Which free wordpress theme has good SEO characteristics? I mean where the main column is near the top of source order and proper use of h1 and h2, etc.
As of now I am using pro-sense theme and is so far good. I just do not know exactly if it is good for SEO.
I don’t know why but I’ve noticed and I’ve read that google really likes WP which is good start. If you want to use some free WP theme I guess the best solution is to choose the most simple one and optimize it.
All-In-One SEO plugin is very good, i using it 
All the new themes that we get are SEO friendly as the developers started giving more attention to this.
As other poster said, All-in-One SEO plugin is a great pluygin and I use it on all my blogs.
Excellent and must have plugin for every wordpress blog!
All most all themes should be good SEOed if you use a plugin all-in-one SEO
Check out the All-In-One SEO plugin. Pretty comprehensive coverage. http://wordpress.org/extend/plugins/all-in-one-seo-pack/
Themes themselves? Most popular themes are marketed for their SEO compliance. I’ve dealt with a lot of themes and the only way I could imagine getting a “bad” one is at one of those free theme aggregators.