Does Google record search / source IP [/ user] pairs? What if my Search History is off?
Yes, maybe, no... Only some Google' employee can answer the question, even then they might give you false information.
A lot of sites and users out there are taking the assumption that Google and other major sites, are taking as much record as possible. For example Eli Pariser talk on filtered bubble suggested that Google is/could take track from 57 signal including web browser being used and where the computer is located.
"Usually your searches are saved along with the date and time of the search, some information about your computer (e.g. your IP address, User agent and often a unique identifier stored in a browser cookie), and if you are logged in, your account information (e.g. name and email address). " DuckDuckGo Privacy
Even if you are not logged in, Google can/could use several methods to identify you over time, again only some Google employees or someone who has solid proof can verify this.
How to create a basic extra layer of privacy/anonymity when dealing with Google?
Stop using Google, but I wouldn't recommend that maybe balance queries between two search engines like: DuckDuckGo which in short it is a beautiful, customizable search engine, but I have had better luck finding things with Google. DuckDuckGo has worked for me when doing simple queries (such as 'New York Doctors).
Still Want To Use Google?:
Customize this as fitted to your needs:
Browser: Firefox Why Firefox? As of Jan 2011 W3C reports 37.1 % of users use Firefox, followed by Chrome 35.3 %. Making it the most used browser, the less unique the better. I recommend Firefox if you are trying to prevent Google to record any relevant information that might identify you.
Proxy: If you have security expertise you might have heard of Tor or have used it before. Wouldn't recommend to always use it, except when you don't want certain personal information to be record.
Track Request Blocker: Disconnect
HTTPS: HTTPS Everywhere
Once more, I am not able to answer your exact answer as I am not a Google employee neither do I have evidence to say Google is recording your searches. But I have given you some ideas on how you can create an extra layer when dealing with delicate/personal queries you wouldn't want to get recorded.
When you use our services or view content provided by Google, we may automatically collect and store certain information in server logs. This may include: