Die meisten Spitzeleien von Webseiten kann man aber zumindest erschweren, wenn man regelmäßig seine Cookies löscht und am Besten nur Webseiten denen man traut überhaupt erlaubt welche zu setzen. Bei den meisten Browsern kann man das ja einstellen, lediglich der Internet Explorer kann das AFAIK von Haus aus nicht. Dabei sollte man allerdings bedenken, dass nicht nur die Seiten selber Kekse verteilen, sondern oftmals auch die darauf befindliche Werbung.
Auch das Ausführen von Scripten (etwa Javascript) nur auf Seiten denen man traut zu erlauben kann hilfreich sein. Dies seitenspezifisch festzulegen geht AFAIK aber zur Zeit nur mit Opera, für Firefox gibt es jedoch ein
Plugin dafür. Auch wenn einen der Schutz seiner Daten nicht interessiert kann so etwas sinnvoll sein, denn auch von Kriminellen geknackte und Schadsoftware verteilende Seiten machen dies meist mit Hilfe von Javascript oder ActiveX (letzteres betrifft nur den IE).
Falls man nicht viel über sich preisgeben möchte, sollte man konsequenterweise auch Seiten wie MySpace, Facebook oder andere soziale Netzwerke meiden oder zumindest nur die Details über sich preisgeben die wirklich jeder auf und außerhalb der Seite wissen darf.
Was das lange Speichern von Suchanfragen betrifft, so tun dies eigentlich alle größeren Suchmaschinen. Ausnahmen von der Regel sind etwa Ixquick oder MetaGer, diese speichern die Suchanfragen lediglich für 48 Stunden oder weniger.
Allerdings auch wenn man Google nicht nutzt heißt das nicht, dass die Firma nichts über einen in Erfahrung bringen kann, auf die Dienste von Google Analytics greifen auch viele andere Seiten zurück. Wenn man das Firefox-Plugin NoScript nutzt merkt man schnell wie viele Webseiten das sind.
Google Desktop Search sendet seinen Suchindex an irgendeinen Server? Ich nutze das Programm zwar nicht, aber das wäre in der Tat unschön, sofern es stimmen sollte.