Which is the best theme for Wordpress from an SEO point of view? Actually, which is the best free one, and which is the best premium one?
For premium I would suggest Thesis. It's very SEO friendly out of the box w/o any plugins installed and even more so with plugins installed.
Free Wordpress Theme - http://wordpress.org/extend/themes/atahualpa Premium Wordpress Theme - Thesis Theme
You need All In One and Google XML Sitemap. The themes mentioned are good (even default) but it isn't the theme so much as the architecture that matters. You need a plugin and permalinks to set canonical URLs, category/tag access, sitemaps, etc.
While you were talking about themes Alex does bring up a good plugin to use as well. Either All in One SEO (which is what I use as well) or HeadSpace2 (Which I hear great things about.) Though I don't agree with "All in One SEO plugin resolve all problems for seo." it is enough for the majority of bloggers. As you brought up themes though, if you look into Thesis on the premium end of things you'll easily find a lot of information on why it is useful SEO wise.
Best themes for SEO are those respecting all W3C rules, mean javascript rules, css, links, pictures .. Everything. You better do visiting newwpthemes.com, I'm using them, they are just perfect for everything.
I think theme doesn't affect SEO technics but I like to recommend you any wordpress themes for SEO because wordpress has lot's of plugins with best features, which can help in SEO.
If you don't want to use any SEO plugin and want all settings in theme, then i recommend Fresh Life Theme. It allows many settings that help in SEO and it has Google+1, Facebook Like and tweeter Tweet by default and many other features.
I prefer to use default themes from wordpress, ligher and less ads from advertiser..just add some plugin that support SEO and promote your blog recently... just my opinion.
Thesis is really great for seo as it saves you the plugin part. All the other frameworks have picked up as well in the past months, so I would say it doesn´t matter so much anymore. Wordpress itself is pretty well optimized. There also good premium themes over at theme forest that are built with good seo in mind.
Thesis, Genesis, Headway and the list goes on. All the Premium themes comes with good SEO and alternatively you can use SEO plugin (developed by Yoast).