Did you see the analysis of the AOL data leak? There is one particular woman in there where consecutive queries and a little editing show a story of her relationship with an abusive boyfriend, accidental pregnancy, abortion, and remorse.
People found it by, essentially, just grepping a flat text data file for terms they knew were likely to resolve to a hot button issue, then separating the wheat from the chaff. This is the "solution you can knock out in vi in ten minutes" answer. If you have a team of Google-style engineers, a large volume of search queries with unique IDs on them, and a Hadoop cluster available, you can make sift-and-winnow as many gigabytes as you have down to as few salient details as you want.
Trivial example: I would stake money on being able to correctly identify the gender of over 80% of users given 100 searches from them, and I would be able to do this with less than one day of programming. If you let me do it in other than realtime, I would be able to do this at terabyte scales using EC2 and Hadoop. And I'm just a guy who did natural language processing in college and has a bit of basic web-fu available. Think of what you could do with a talented engineering team, deviousness, and a few months to work on it.
If you move (change IP) Google will be able to track you if you use any of their sign-in services (example@gmail.com now regularly logs in from this IP instead of the old one). Your only chance of breaking this chain is either to regularly use proxies or to change IP and gmail (and other services) simultaneously.