VPN (Virtual Private Network) is a term for a range of technologies that allow you tunnel private network (LAN) connections over another network (eg, the Internet). This allows you to communicate with machines over the Internet as if they were on your local network.
Popular VPN technologies include;
PPTP ← broken
Ipsec
OpenVPN
A popular use for VPNs is the use of “VPN service providers”, these are companies that (for a fee) allow you to tunnel all or some of your usual Internet traffic though them by use of a VPN. This allows you to shift the trust you give to your local ISP to another ISP (VPN provider) of your choice. Reasons someone might find this useful is if their own ISP engages in logging or data retention or if they cooperate with requests from “rights holders” to provide the names of “copyright infringers”. The use of VPN services with shared ips might also help you to obscure your identity from advertisers and trackers. VPN service providers should not be considered a viable way to achieve anonymity from organizations such as the NSA/CCHQ/CSS/DSD/BND or FBI/INTERPOL. Even if a provider is able to stand up to such an adversary both legally and technically there is still nothing stopping them from simply monitoring the upstream provider and correlating the traffic going in to the traffic going out over the single hop, this is trivial. There is also evidence that cryptographic attacks exist, though the technical details are lacking or absent, seems one of their most popular methods is to simply 'go around' by stealing keys and other indirect methods.
When choosing a VPN service provider the most important things to look at (aside from price, b/w and datacaps) are;
The privacy policy: this will lay out what information they keep about you and how they can use it.
The Location: Depending on the location, both where the business is based and where the servers are physically located, certain laws and regulations may apply to what data they are required to log, for example many countries have mandatory data retention laws that require isps to log everything and keep it for a certain length of time. Other countries such as the United States have no mandatory data retention law (?do they now have this, or is that just for phone calls?) but a court can require a specific isp to start logging in secrete regardless of what is stated in the privacy policy.
When choosing a provider make sure they use OpenVPN and do not use their custom clients, these are usually closed source and entirely pointless, just use the free software OpenVPN client software https://openvpn.net/index.php/access-server/docs/admin-guides-sp-859543150/howto-connect-client-configuration.html
There are various 'lists' floating around of 'the best' or 'the most private' providers, I don't know how much it costs to get on one of these lists but it's probably not a lot, I will not make any recommendations (unless someone wants to pay me too :^) ) on providers myself, any of the big name providers should offer decant speeds and will prevent threatening letters from 'rights holders' turning up in the post.
A popular alternative to using a VPN service provider is to rent a VPS (virtual private server) or similar hosting and configure that as a proxy (using OpenVPN or socks5 or similar). The same theme applies here, read the privacy policy of the hosting provider and understand the limitations. Using a dedicated server (or VPS) to proxy your traffic in this way will differ in effect to using a VPN service provider in that you will not be using a shared ip addresses, so it may be more easy to correlate your various communications to one person (you). This may also help in some way to avoid mass collection/correlation of your traffic because you will not be a known VPS provider therefore perhaps less of a target.