If you have not already done it load a plug in for firefox called ghostery and watch all the alerts. This is antitracking software. My point here is not that you should run out and load this all your problems go away it is more to show how hard it is to really privately access anything. One of the worst offenders is facebook. They have tracking hooks in everything and since they tie it to your real name or at least a phone number they can tie you to lots of different sites. Even google does this. If you log into your gmail account it will then track all your searches back to that gmail account.
A VPN will not solve this. In fact what it will do is tie your external VPN address back to other things that are tracked. If you were for example to ever log into a site from your real address and then use a VPN they could easily tie this together.
You would have to disable all scripts and cookies to prevent this which makes most sites unusable.
Pretty much a vpn is only good to get around regional restrictions say to watch video or play on certain game servers. It does not really prevent sites from really locating you. They just choose to pretend they don't know you are coming from a VPN site. They want your money and in most cases it is not their choice to put content restrictions based on location so they just pretend they don't know