I spent the past 2 years working exclusively on large e-commerce sites. E-comm sites can be the biggest headache, but after learning from the mistakes of others (and my own) I now have a company that exclusively works on large e-commerce sites.
The core principles of SEO are what makes e-commerce sites such a bitch, there is little to no reason for anyone to link to an e-comm site. If you are running a site that sells products from multiple manufacturers, that is another migraine, the data that you get from the manufacturers is crap, complete garbage, and order fulfillment with multiple drop shippers - total nightmare. But, once you get the wrinkles ironed out, e-commerce site marketing is amazing.
The high dollar link company, webuildpages.com has a bunch of e-comm clients and they charge $2500 a month for 10 backlinks from high PR and .edu and .gov sites. I don't know if their methods have been discussed here before, but I paid them for a few months last year to see what they were doing to justify that price tag. They got the links, but 9 months later, there still hasn't been a noticable effect or natural link growth.
CSE's are the way to go for e-commerce sites. 70% of our revenue came from Google Products. PPC is almost totally unmanageable if you have more than 10,000 products - the 80/20 rule certainly applied here. There is still one 'trick' that works extremely well in PPC , but I watched that slowly start to fade when Google caught on and clicks went from .10 to 6.00
For sites with thousands of products, its all about Excel formulas and using offshore companies (like mine

) to work on the data like an assembly line. Also using the webuildpages method of link building still works for domain authority, but soon it will not.
Integrate information into the product pages and do not use canned product data thats provided from manufacturers.
On-site search should be a TOP priority. If you are serious about your ecomm site, you have to invest in powerful and configurable on-site search solutions. I have used the Google appliance and several other companies and there is one that really stands out as the winner. Hopefully you have your analytics setup properly to track on-site searches. If you are using a CMS like Magento, be ready to do some development work.
3rd party carts are hit or miss, personally I have used 3dcart for a few cheap clients recently because of the built in features - but it definitely has its drawbacks as well - If you take a look at the shops using 3dcart, you will see some truly disastrous practices in play.
Don't use subdomains if you can help it. Isolating your eommerce store in a subdomain , away from any content with substance is a mistake.
Reviews and testimonials are absolutely key, and hard to get when starting out. Google loves them, visitors love them.
Navigation, Taxonomy, and usability are the most important thing. I used to want to believe that there was some kind of loyalty with buyers online, but there isnt, its just pricing. Who is the cheapest and then who is the easiest to navigate. If you aren't A/B testing your pages, watching visitor engagement, and always optimizing your checkout process - you're nuts.
I discovered something HUGE last year, a complete game changer for all of my e-commerce clients - inexpensive to implement and absolutely invaluable, well actually it could be valued, it was responsible for a HUGE spike in ROI on every clients site. Unfortunately, I can't say what that was until I work out a way to get paid for cluing people in.