How can I search in a way in Google that prevents my search terms being linked to my identity (cookies, IP ...)? I know there are some tools such as a Firefox extension that makes random searches from time to time to "drown" the real searches among fake ones.
You could use the 'incognito' mode in chrome, or the 'InPrivate' mode in IE, and then use https://www.google.com to do the search.
This would (somewhat) protect your searches locally, and if you don't log into any google accounts while in incognito mode, it should protect you from having your searches tied to your id in google.
use Tor and delete all cookies in your browser after each session.
one option would be something like Hidemyass.
If you are really paranoid, boot a live distro of Linux from CDROM, do the search and switch off the machine :-)
Until yesterday you could have used Scroogle, but they're having problems right now.