I'm not sure this is a really a Craft-specific question, but here's a basic strategy:

1. Build your nav and pages to work without any Ajax calls. Make sure your nav is output consistently (e.g. in `<nav class="primary-nav"`) as well as the content of the page (e.g. in `<div class="main">`). 
 
2. Now implement your JavaScript. You want to (a) intercept navigation link clicks to stop a full page reload, (b) Ajax in the new content, (c) move the `active` class to the clicked navigation link, and (d) change the URL to the new page address. Make sure to use [history.js](https://github.com/browserstate/history.js/) to smooth out any difference in browser implementation of HTML5's history API (including pushState).

Here's a [demo](http://jmuspratt.github.io/hijax-demo/) (and [code](https://github.com/jmuspratt/hijax-demo)) I cooked up with static HTML. It's based on Andrew Fricke's post titled [Rolling your own PJAX Implementation with History.js](http://uhnomoli.com/2014/01/10/Rolling-your-own-PJAX-implementation-with-History.js/)