I've been playing with Microsoft's search engine, and so far I like what I see. Search results have been pretty high-quality, although honestly I haven't really put it to the test. Most of my websites are ranked roughly the same as they were using Google organically.
I've also been reading about the experiences of other top-level SEOs that I respect.
Generally, here's what we have discovered.
Content Continues to Be King -- You must have great content. This is critical with any search engine. High quality content and lots of it, and having that content well-organized, is critical to your success.
Keyword Placement -- Keep your keywords in all the right places. Page titles, headline tags and linked text are most important. It seems to me that bold print and italicized text don't earn you the respect they do in Google.
Inbound Links -- One significant difference seems to be inbound linking. It seems to be critically important that authoritative sites link to you. Google seems to favor quantity, while Bing looks for a nice mix of quality and quantity. Google has been trending this way gradually, and Bing seems to have taken it further.
Validation -- The value of validation of your code is undetermined however Microsoft explicitly recommends it. Ironically, Microsoft was dragged kicking and screaming into the W3C. For years the biggest frustration with Web developers was the IE 6 didn't use standard protocols. IE 7 finally embraced website standards, and now it seems Bing may actually prefer sites that are validated. Try to get rid of broken links and redirects whenever possible.
Standard HTML -- Microsoft recommends static HTML pages rather than dynamic URLs. This could be a big hurt to companies that use a CMS to manage their websites and generate PHP or ASP pages. This doesn't surprise me considering Microsoft's failure to embrace PHP in general.
I'm still a huge fan of Google as a company, and I still am wary of anything Microsoft. However, I do think that competition is good in the realm of search engines. It's going to force Google to continue to develop their product. I would like to see two or three major companies and a handful of smaller companies with real competition for search engine users. It's going to give website developers more opportunities, and marketers more choices in advertising.
Furthermore having strong search engine results means that it will stave off Web 2.0 as the dominant factor in quality traffic. It's important to have a nice mix of social networks, advertising, social media and search engines each contributing traffic to your website.