"Maybe you shouldn't do it [...on Google]. Or, [...on the internet]. Or [...in a way that people can find out].
The idea is that privacy is difficult on the Internet: your ISP knows what you're doing, your search engine knows what you're doing, etc.
So doing something online without telling someone about it is really really hard. So if you don't want someone to know about it, basically your only choice is to not do it [online].
It's not that creepy and it's not the typical privacy fallacy everyone thinks it is (the "if you're not doing anything wrong then you have nothing to hide" bullshit)
I read Eric's answer along the lines of "Look, as CEO of the company, I think it's important to know that treating Google as your best friend would have limitations, specifically (the whole Patriot Act stuff)."
"If you really need that kind of privacy, the reality is that search engines - including Google - do retain this information for some time and it's important, for example, that we are all subject in the United States to the Patriot Act and it is possible that all that information could be made available to the authorities."
So in context, he's basically saying that of course if you're logged into google, surfing from your same home IP, well duh, of course Google, or the government, or your ISP, or some random hacker can figure it out. You can't guarantee privacy without using something like Tor.