Edward N. Albro writes about his experience setting up a google search history for himself. Surprise! He finds his old searches back to Dec. 2005, even though he didn't opt in until now.
WORSE yet, I notice in the google FAQ that you can get your (or presumably anyone's) search history via RSS feeds. You need the person's username and password, but who knows how strong those are.
On the one hand, google search history can be far more invasive into your mind than library records.
On the other hand, google users opt in, sort of. As I understand it, search histories are only available for people who already have some type of google account, like gmail... and who use the google toolbar. But do gmail users know that their histories are out there, available to anyone who knows their username/passwords? Sounds like you no longer need to get your hands on someone's actual computer to look at browser search histories. At least if you're a google account holder, and know about this, you can "pause," edit your search history, or opt out altogether.
Library users, however, don't have a choice but to leave a trail of library records of current items, holds and fines. These records are all potentially available via RSS with only a library card number and weak PIN number to protect them. Libraries need to offer strong PIN numbers to those users who care about their privacy.