En principio cuando uno navega por internet la navegación es anónima. Quiero decir, cuando tú haces una consulta le envías la IP al servidor, pero las IP no son para nada fiables y en general se guardan, pero tal dato no es relevante.
Por otro lado, tampoco existe realmente una conservación de estado en la consultas por lo que se inventaron las cookies. Estas cookies son pedazos de información que el servidor envía al cliente (nosotros) y que nosotros envíamos al servidor cuando se nos pide.
Por ejemplo, si tú te logueas en gmail, gmail te envía una cookie con tu Id de sesión y una serie de datos para identificarte como usuario único, para que no tengas que estar logueándote en cada consulta. Esta cookie el servidor puede pedírtela cuando quiera y tu navegador (Internet Explorer, Chrome o cualquiera), con lo cual, siempre que hagas una consulta el servidor sabrá quien eres.
En el caso de las consultas de Google, este te envía una IP tanto si estás logueado como sino y así sabe tus preferencias. Estas preferencias las guarda en una base de datos y así al día siguiente, sabe lo que buscaste ayer.
Si no tienes cuenta de Gmail, si te vas a las opciones de tu navegador y borras las cookies, para Google serías un usuario nuevo, porque no podrías enviarle esa cookie que te pide.
Si tienes cuenta de Gmail entonces siempre sabrá quien eres, siempre y cuando te loguees.
Respecto a lo de leer los correos es algo que Google lleva haciendo desde el principio de Gmail, no es nada nuevo.
Ahora me tengo que marchar, pero el lunes, podemos hablar de minería de datos.