The quote "If you have something that you don't want anyone to know, maybe you shouldn't be doing it in the first place" reminds me of the position people take regarding privacy and over-reaching government snooping that violates the 4th Amendment. "If you're not doing anything illegal, you should have nothing to hide." "
In that quote, Schmidt was referencing the government's ability to demand your information. Google had recently lost a court case about it, which is why he brought the subject up.
A lot of privacy crusaders seem to mix up private and public information, though. Whatever you do in Wal Mart is public, and you can't demand that they erase all footage of you from their security cameras and make every employee that saw you forget that you were there.
Similarly, if you freely give information to Google, like search terms and your IP address, should you be able to force them to forget it?
Sensitive personal data -- SSN, bank account numbers, etc. -- I can understand special provisions for. But your unhealthy Febreeze obsession? The only thing protecting you there is your obscurity and Wal Mart's desire not to drive you away .