@gourimoko how do you get around this?
As a guy who has been a Google fanboy for many years, the more I read about em, the more I'd like to avoid them.
You have to mask your presence.
Google tracks you using several indicators. These indicators propagate what search engines call "signals."
Some signals are louder than others, but in general there is an algorithm that attempts to identify each and every user, down to exactly who they are (name, dob, age, address, everything).
The indicators include your hostname (in Windows this is equivalent to the name of your PC); your IP address (this is a weaker indicator); cookies resident on your computer (biggest indicator there is); Google Chrome's internal cookie; MAC addresses (particularly for mobiles).
Signals include what pages you browse to directly versus those you search for. The time you spend on particular pages, duration, etc. Common search terms, etc.. For example, I might have a uniquely identifying signal like so:
1) Has RealCavsFans.com open (think of how this narrows down a search of 6B people).
2) Opens newscientist.com
3) Searches stackoverflow.com
4) Periodically browses to DailyKos.com
These 4 signals (just as an honest example), can uniquely identify me, the unlogged in user that has no identifying cookies and I've masked my IP or used a VPN with end-to-end encryption. Doesn't matter, Google knows, this is probably "Gourimoko," but at the most this is probably 1 of 3 people on RCF, including me. Add one more signal and the probability is that you've narrowed it down to the individual.
If using a mobile phone; forget anonymity in most cases. To hide from Google, you'd need to root the phone, install a cronjob to generate a fake MAC address for the LTE radio and mask the real MAC with the fake one (and this would need to rotate often). This is generally outside most users time/effort constraints, although it's not terribly difficult.
From a home device, you can get pretty secure. Using a VPN is a good way to start. But the moment you log into gmail, Facebook, Instagram, YouTube, your bank, anything from that IP, you've then married that IP to your personal identity. Sure, not every site reveals your identity to Google, but almost all of them do; like literally, more than 90% of commercial sites share data with Google to track users.
If you need temporary security, and do not need a fast connection, downloading the Tor Browser (Aurora) is a way to obtain quick/fast anonymity. Logging in to gmail this way is safe, just don't immediate do something illegal (it's best not to do anything personally identifying the same day you do something less than legal on the Tor network).
Hope this helps.