A nice solution here is to have a 'traditional' application with new page loads for links, so that search engines can follow them. You then enrich this application with Javascript, placing click handlers on the links to replace their default action (loading a new page) with a similar action performed through Javascript/AJAX.