Yes, it does
Even if you delete your cookies, and your IP address changes, whatever new IP address you are assigned, will still identify the city you're coming from. I've demonstrated this to others several times, by clearing all cookies and rebooting the router, then doing a traceroute to google.com. The first address in the list that appears is your router's LAN IP (eg 192.168.0.1), the second address is your ISP, which in my case gives a result like lns20.adl6.internode.on.net [203.16.xxx.xxx]. That tells anyone with a half-decent geolocation database that I'm in Adelaide, Australia (as well as the fact that my ISP is Internode!).
So Google can still be very effective at determining your location (and therefore tailoring search results to it), even if you have your privacy settings up the wazoo and reboot your router every 10 minutes.
What's even scarier is the way you can be statistically identified using a Flesch-Kincaid readability test. In its simplest form, this test simply establishes how readable anything you write is. With a bit of further analysis, however, a machine can use an F-K based algorithm to recognise specific styles of writing and spelling and deduce the statistical probability of a certain person being the author of whatever is typed, once it's 'learned' that style (such as the style of my writing in this comment!) And I've seen examples of this test being pretty damned accurate - on the order of 75-85% in a class I was in a few years ago. It nailed me every time because of my distinctive writing style.