How can you use themes (and templates) to change the look and feel of an install

I'd like know more about how to theme sites, and perhaps make templates, to change the "look and feel" of Drupal sites. I'm getting a whole lot of "push back" regarding what some consider the "ugly" standard look of a Drupal.