The site you linked to isn't updating the nav menu with AJAX, rather, when you click a link they load the target via JS then swap the entire page for the new page.
A little bit of trickery with pushState ensures the URL in the address bar changes and back/forward is preserved. Take a look at the term PJAX, there are JS libraries that implement it, and it may be a more useful search term.
Otherwise your options are limited. If you're building a SPA, you will want to construct your menu and use browser history/current URL to figure out which element to style