Data collection
I'd imagine most search engines will collect some data on user searches beyond logging that someone, somewhere in the world, at some point in time was motivated to search for Hello Kitty. Your IP address, browser, OS and possibly screen resolution are automatically made available to every single site you visit; so in the interests of collecting demographics about their users many sites will log that information. With Google being a major ad-broker, it might also be able to log whether you're blocking its ads or not.
Of course, if you sign into Google when you use its search engine, it will be able to isolate you, even if you use multiple computers to use it.
That's pretty much par for the course for most businesses / websites. So I suppose one way Google could address concerns is to produce a page somewhere stating what data was collected, which bits of data collected were tied to individual users and which were automatically aggregated, and what the data was used for (in more specific terms than the general cop-out "improving the user experience").