¿Google conoce mi historial de navegación por el hecho de que mi teléfono esté vinculado a mi cuenta de Google?

El título de tu pregunta suena como si estuvieras hablando de la función "historial web" de Chrome. Cuando navegas con Chrome (ya sea en tu dispositivo Android o en el escritorio), o desde las búsquedas de Google Now, las páginas que visitas se registran en el historial del navegador. Chrome sincroniza el historial del navegador con los servidores de Google para que puedas acceder a él desde cualquier equipo en el que hayas accedido a la misma cuenta de Google y para otros servicios de Google como Google Now.

Si no quieres que tu historial de navegación se almacene en los servidores de Google o que se utilice de esta manera, ve al Configuración de Google aplicación, haga clic Cuentas y privacidad y apagar Historia de la Web . (Como señala el Sr. Kutch, también hay una interfaz web.)

Si utilizas otro navegador que no sea Chrome, como Firefox u Opera Mobile, Google no tendrá acceso a tu historial de navegación.

El modo de incógnito debe tenerlo cubierto si no quiere que su historial se vea dentro de su navegador. Asegúrate de limpiar cualquier archivo que descargues (imágenes, videos. etc.) ya que tienden a aparecer en tu galería de fotos una vez descargados. Puedes gestionar los archivos con la aplicación "Mis archivos". El S4 también tiene una aplicación de "Descargas" que mantendrá un historial de los archivos que has descargado tan claro que también. También asegúrate de revisar tu Historial web de Google si alguna vez lo has activado.