A member poses a question about Google cookies and describes an experience in which Google seemed to be tracking every search result site visited, until the cookie was deleted. The member also notes that there seems to be an ID number in the cookie that uniquely identifies the user, while such an ID number is not necessary for the storage of 'preference' information. GoogleGuy responds to the URL redirection (tracking), but he doesn't address the ID number issue.
[Link to quote
(It's in the "Links to Other Sites" paragraph.)
For what it's worth, many search engines track every click, instead of only a tiny sample of clicks as a spot check. I think AV and ATW always do url redirects but use mouseover code to make it look like the clicks are direct, for example.
[P.S. Searching on Google will work fine if you want to disable cookies. We just won't be able to store your search settings/preferences.]