Lógicamente se usa Ajax, al hacer click en algún enlace en lugar de direccionar a donde apunta, tomas la ruta y la envías mediante ajax para tomar el contenido de esa dirección, se procesa para seleccionar solo el body o talvez alguna sección que se sea la que se deba actualizar. Bien, "imprimes" esa sección mediante un innerHTML.
Ahora, si haces eso te ganas el problema de los botones de atrás y adelante. Eso se puede arreglar con JavaScript y existe una librería que ayuda en eso e implementa las dichosas variables con #.
En cuanto al SEO, eso no es problema si se hace como lo planteo. Todas esas páginas existen con su respectivas ruta y si se ingresa por esas rutas entran igual. Solamente hace falta redireccionar con JavaScript a la página respectiva de acuedo a las variables con # cuando se hace un refresh.
Esa sería la forma. Aquí hay algo de información sobre esa librería que soluciona el problema de los botones atrás y adelante.
http://www.unfocus.com/projects/historykeeper/