Antes se solia hacer con iframe superpuesto xD. Ahora estas cosas se hacen con javascript.. ajax para ser exactos.

Si te fijas:

exafm.com/#!/mexico/home

En azul es la direccion.
En maron es el separador que utiliza javascript.
En verde es la ruta de la pagina en la que estas.

Cada vez que cambias a una pagina, solo cambia el verde que en realidad no es mas que una ruta "virtual". Tu navegador nunca llega a recargar/cambiar de pagina, todo lo hace una consulta ajax. Te puedes dar cuenta de ello, porque si desactivas el javascript de tu navegador, la pagina entera deja de funcionar..

Básicamente, mediante ajax, actualizas/cambias solo una parte del html y así no tienes que recargar la pagina entera.

Saludos

No deberias tener problemas con Google (al menos) porque fueron ellos los que lo propusieron como un estandarte para las aplicaciones ajax xD.

https://developers.google.com/webmasters/ajax-crawling/
http://googlewebmastercentral.blogspot.com.es/2009/10/proposal-for-making-ajax-crawlable.html

Pero bueno... lo normal seria tener un fallback server-side que se encargue en caso de que el visitante(bot o persona) no lleve javascript activado.

PD: Creo que este tema se discutió aquí hace tiempo pero no me acuerdo del post xD...

Saludos