Semantic mark up and clean URLs are a big part of SEO. But there's a lot more to it. There is obviously the whole incoming links thing as a few other comments have mentioned.
The biggest issue that I see on client's sites is site architecture, organization and internal linking. Most commonly that means multiple pages with the same content and different URLs. Amazon is a good example of this:
This URL floats around internally - http://www.amazon.com/gp/product/1416571760/
But it's rel="canonical" is http://www.amazon.com/Greater-Journey-Americans-Paris/dp/141...
Amazon is essentially passing internal link juice around to non-canonical URLs, then "fixing" it with a rel canonical hack. Not that amazon needs the link authority, it's just an example.
Another good one is folks who append things like ?ref=category to a URL to track visitors through the site. That's a unique URL to google, though you can specify what url parameters are legit in webmaster tools. If you really need to do something like that, use onclick events and keep the href attribute to a pretty, canonical URL.
Those don't seem like big issues individually, but imagine a 3,000,000 page site that never links to a canonical URL anywhere internally (this happens).
Internal anchor text can also play a roll in what you rank for. If you happened to make it through all that stuff up there, here's an SEO gem: use breadcrumbs, but your home link doesn't need to have the anchor text "home". Instead use a keyword that's relevant to your site's purpose. If you sell dog food, use "dog food" as the anchor text of "home" breadcrumb link.
An example: do a search for "online shopping" on Google. You'll probably see overstock.com in the top results. Why? Are they really more well known and authoritative than Amazon in that arena? Every home breadcrumb on overstock.com has the anchor text "online shopping". Millions of internal links with perfectly optimized anchor text pointing to a single page.