I second David on this point. I use iGoogle extensively and its Web History shows me all of the searches I ever made since I signed up - which is fantastically useful when I'm trying to remember the URL for that news article I searched for three months ago that has long since disappeared from my browser history.
Yes, anyone getting access to that data would be able to build a really detailed psych profile on me, but with millions of users why would they bother targetting little old me? There's a difference between being privacy-conscious and being paranoid, and when you come to think of it, it's not only Google storing your searches and surf history - your ISP is just as capable, if not more so because they can track sites you visited without even going to Google. And most websites track user data as well - as a Web developer myself, all of the sites I develop have user tracking capability to some extent, including storing search queries where applicable, because this data allows you to determine important information such as product popularity, demand, consumer demographics and so forth. Without this information, it's almost impossible to run an online business effectively. It's an essential way of staying in tune with your market. Every site does it. Get used to it.
As to the "immortal cookie", that sounds like Daniel Brandt agitprop to me - he's fond of using that term. There's no such thing as an immortal cookie. You can set your browser to automatically clear all cookies on session end, or you can manually clear your cookies at any time. Most browsers also support additional cookie-control options such as blocking cookies by domain, so Google have no way of forcing you to accept or retain a cookie if you don't want it. It's there so the site can remember your preferences and work the way you want it to.
@SpitefulGOD: If your girlfriend is data mining your search results, it's because she doesn't trust you. That's a relationship doomed from day one. Trust me, get another girlfriend. Seriously.