google has "google profile" feature. If you enabled it you'll be able to customize search page, news page, and they'll keep history of everything you ever searched for (feature called "Web History"). "Web History" is very useful, in situation when you want to know what was that article you found at certain date of last year and can't find now and don't remember keywords. Of course, as public mail servers and nearly everything else on internet, "Web History" could be misused against particular user.

and you some how have to use that in order to use google's search engine? I could see if you were forced to use that in order to use the search engine, but you don't, so if I go on a random public computer, its not going to steal my SSN, or my mother's maiden name

You aren't forced. But you asked about mechanism "how they could store your information", so here it is. Also if you use static IP, your search request can be easily tracked to your machine. Besides, public computer can be infected with trojan/keylogger.

People, if you are paranoid about privacy, don't do anything that could make you too interesting to the government. Or someone else. And if you want to know how carefully "they" watch you, simply search for something like "how to make a bomb" with google (I really think nothing will happen). There is illegal cr@p on the internet and there are a lot of people who purposedly search for this cr@p. But I don't think that government(or someone else) track down each person. Instead of worrying about online privacy, I'd think/worry about security cameras in banks, shops and on the streets. Those are larger threat to your privacy, IMO.

How many people using a web browser (any web browser) know how to delete cookies, or even what one is? Just because you'd delete it doesn't mean everyone would, and those are the ones Google cares about.

well, if you are really paranoid that google is trying to take over the world, then you would obviously know how to delete a tracking cookie

I'd ask it another way: How many people using a web browser know what is "web browser"?

Google can't take over the world alone. It needs to merge with wikipedia and jabberwacky to be come skynet

That would be a great day, but what would be its motivation for starting the war ? Maybe it would get sick of all the stupid things people search, and decide to end it all.

that's a good one.

IMHO, it has everything I like about Chrome! (except the sandboxing)
http://labs.mozilla.com/projects/prism/