That's not how cookies work, cookies are stored on, and controlled by, your client. Unless your client is sharing the cookie information across devices, google wouldn't be able to track you across devices using cookies. Routing all of your searches to one machine allows google to build a richer search profile against you, rather than one scattered across multiple different IPs, device fingerprints, etc.
I assume you mean across the web? That too is more of a different issue, as it is unrelated to the use of google search itself, rather it is due to the existence of tracking services embedded into the websites you visit.
At the end of the day, your VPS is still having a search profile build against it, in a similar manner to just using your personal device. The main difference is that you are paying to have a specialized computer that serves as a single purpose google searching device. Perhaps it is more challenging for them to link that device directly to you specifically, but I'd honestly bet that it is achievable.