If you want it to work in browsers that don't support history.pushState and history.popState yet, the "old" way is to set the fragment identifier, which won't cause a page reload.
The basic idea is to set the window.location.hash property to a value that contains whatever state information you need, then either use the window.onhashchange event, or for older browsers that don't support onhashchange (IE < 8, Firefox < 3.6), periodically check to see if the hash has changed (using setInterval for example) and update the page. You will also need to check the hash value on page load to set up the initial content.
If you're using jQuery there's a hashchange plugin that will use whichever method the browser supports. I'm sure there are plugins for other libraries as well.
One thing to be careful of is colliding with ids on the page, because the browser will scroll to any element with a matching id.
@Drew, as far as I know, there's no way for search engines to treat a part of a page as a separate result.
Instead of using setInterval to inspect the document.location.hash one can use the hashchange event, as it's much more adopted. Check here for what browsers support each standard. My current approach is to use push/popState on browsers that support it. On the others I set the hash and only watch the hashchange in supporting browsers. This leaves IE<=7 without history support, but with usefull permalink. But who cares for IE<=7 history?
@gabeDel Yes, although I don't think Analytics records the hash, so it would have the same URL. A better way would be to manually call _trackPageview with the "real" URL of the new page.