Have you found and explored the Google Search Education  website? I was lucky enough to have reference maven Carole Leita  remind me today that not only is it still out there, but it's been beefed up to include lesson plans (shared under the Creative Commons licensing  that allows reuse and local editing as long as there is correct attribution).
The plans and other help pages at this site, that carries the tag line "Search Education Evangelism," include those targeting basic users, pros, and Google users by specific country (You have to be approved to access the documents designed for other countries; not all of these are Web enabled). The basic lesson plans are scaffolded from beginner through advanced, with the most basic lesson  offering both directions for an instructor and a slide set to use when working through the differences among "Internet," "Web," "browser," "search engine," etc., terms that many of your library's computer users may never have paused to understand clearly enough to effect good searches (or clear reference questions).
So, Google may be impinging on privacy , but at the same time, let's not look this empowerment gift horse in the mouth. Start with your staff and help them to bring more clarity and understanding to advance searching (that is, library added value searching!) in response to users. But also share with your users directly.
Google's willing to empower searchers to get to the heart of their information needs (Yes, the cynic notes that the closer Google users get to their "real" needs, the better targeted marketing the search engine can sell), and certainly we librarians should be working toward that goal as well. Not only can we reduce frustration and ignorance, but we can continue to evolve as the knowledge-exploiting species we are if we can all better clarify "real" answers.
PS My request to be vetted to look directly at the Latin American Spanish documents was answered--by a real person!--in under seven minutes while I worked on this post. I received an apology stating that the set in question is being updated and edited but that the person doing that work is currently on vacation. The human face of Google (and sounds like some library messages I hear, too)!