I settle for just regularly scrubbing the machines from cookies, to make me regularly become a "new" user. Making a lot of searches from NAT:ed IP addresses makes it very hard for Google to try to keep everything together without the internal cookies. But it is important to use a common browser, so I'm not the only one using a specific browser and browser revision behind the NAT.

It is just as important for web sites that either links to common ad servers or visitor tracking servers. No need to have the ad server collecting information that I regularly visit both site A and site B. So if site A is about electronics, then the ads on site B displays ads about electronics. I normally keep a large blacklist in the firewall, to make sure that a lot of tracker addresses can't be reached even if I make use of a browser that doesn't have ad blocking software installed and enabled.