It's hard to know where to start sometimes. First, the cookie doesn't allow google to track anything but the LAST search, and the user preferences. That's all. Folks, it's not tracking EVERY search you made for the last 38 years, only the LAST one. And, like every other search engine, it tracks the LAST one so it can tell which page of it you want to see next -- there's no other way to handle the "next page" request in a stateless system like TCP/IP. If you don't want the feds to break into your computer and find out that you were searching for "Anthrax breeding and distribution systems for rent", then just finish your session by searching for "formal linguistic models of Nahuatl verb participles." Or, if you don't want the "next page" button to work, turn off cookies (or even, using the new browsers, turn off only Google.com cookies). This is not a problem.
Please quit spreading misinformation. Saying this is just as bad as saying Google IS tracking your every search, when in fact you don't really know what they are doing. Personally I don't believe they're doing anything harmful, but who knows. The fact remains that a lot more than your "last search" can be attributed to that cookie. Of course it is not all stored IN the cookie, that is ludicrous. If it was stored, it'd be stored on some DB somewhere keyed to your cookie.
And BTW, TCP is stateful. It is of course built on top of the stateless IP. Did you mean to say HTTP? Which is stateless. But, on top of TCP. Of course we have 1000 ways to keep state over HTTP (sessions...).