In my opinion, there are two main issues to bear in mind when Search Engine Optimizing AJAX:
Problem #1: Lack of content and navigational links on initial page load. This is a problem because the initial HTML page load is all the search engine spiders will see. Search engine spiders do not read JavaScript. Period.
Problem #2: Lack of unique URL's for search engines to index. AJAX makes it easy to serve all your content on one page, just like Flash. Unfortunately, search engines need unique URL's.
However, each of these problems has a solution.
Solution to Prob #1: The initial load of the page definitely needs to contain valid HTML content and navigation.
Solution to Prob #2: You need to think like a search engine spider when creating the structure of an AJAX site. Make sure that they can get to a unique page with valid, quality content. You can still have dynamic pages, but you may want to consider using URL rewrites to create unique Search Engine Friendly URL's.
If you're interested, here's more info on AJAX SEO.