Disclaimer: I find this a very interesting topic, so I've scanned through every single answer, and now I want to summarize here what I've just learned and group all good links in one place.
And make no mistake, Search Engine Optimization today is all about Google, even while people want to avoid saying it (just count words for "Yahoo" or anything else there).
Content is King
"The Golden Rule of SEO: Content is King" is the first thing to consider. It's quite simple: have good content. That's the primary reason Stack Overflow has a chance to rank at Google, simply because of how page ranking works.
Websites that have no optimization or guidelines concerns whatsoever but got nice stuff have a great chance of ranking high, because there will be people linking to good content. And most sites trying to do SEO without content won't rank well because nobody will link to them.
With that been said, Stack Overflow does a lot of work from a long time ago to keep clean HTML code...
Clean code has its value
One good example is how rel='canonical' is applied in here to keep search engines away from linking to duplicate content. For instance, let's get this page source:
<link rel="canonical" href="http://meta.stackexchange.com/questions/14056/seo-in-stackoverflow">
That is an optimization that will not help to directly rank in the search engine, but it will make the results the engine can find much more relevant and through that it might generate more links (from people who found what they were looking for) to the good content it already have, thus actually indirectly improving its rank.
So clean and optimized HTML does work in conjunction with good content...
But content comes first.