This depends on how far you want to go…

…if you just want to change the header graphic, and maybe the colour scheme you will find that K2 is fantastic in that respect (also take a look at Thematic). However if you want to completely butcher the layout – for example change sidebar configuration and maybe have dynamic page/post content then a more basic theme would be appropriate.
K2 and Themeshaper have made all configuration they have available accessable from the dashboard (which is extremely excellent) but the coding for this does tend to make major overhauls somewhat confusing – it is possible but will maybe take up more time than it’s worth.
If you want to build your own theme from scratch then a ‘back to basics’ framework such as Sandbox may well fill your needs.