I can see from an clean request to google.com that they set two cookies on your browser that are set to expires 6 months from the last request to google.com.
So assuming you use google more than once every 6 months they can keep a running log of your searches, and as soon as you log in to any google service with that cookie they will associate it with your account (I'm guessing).
If you clear your cookies reguarly or use incogneto it's not an issue.