When using the internet, you connect to IP addresses. Traditionally, IPv4 is used to accomplish this (you may have seen numbers in the past like 126.96.36.199 or 188.8.131.52, etc). There is another standard that will some day be more prevalent, called IPv6, but that is being used now during the time it transitions into normal configurations (vastly more IPv6 numbers exist than IPv4). When you connect and use the internet (unless you have specifically taken steps to disable it), you are sending and receiving IPv6 data. Again, normally, this data is sent and resolved through your ISP and their DNS servers, but unless properly configured, this information might not be securely passing through the VPN tunnel and could be leaking to the open internet. Given such routed global IPv6 addresses, it's easy for remote sites to identify user ISPs. And with requisite authority, account information could be obtained from those ISPs. Choose a VPN service that either blocks or provides new VPN-specific IPv6 address and provides an IPv6 DNS server that's reachable only through the VPN tunnel - then TEST IT TO MAKE SURE.
Around 1440 AD, the Printing Press was invented. It created a method for the common person to quickly disperse information, technologically reinforcing the natural right to freely speak and share information. More recently the internet allows billions to freely and openly share ideas and advance humanity. This reaffirmed the common person's rights in such a way that was difficult for governments or organizations to stifle. Similarly, until the invention of firearms, only those physically capable could defend themselves from those that wished to encroach on their rights, thus this technological advancement reinforced the individual's right to self defense. This brings us to Computerized Encryption. As with the other technological advancements mentioned above, Encryption provides a simple-to-use method that the average user can take advantage of to reinforce their right to be secure in their persons, houses, papers, and effects, against unreasonable searches and seizures.
Choose a VPN service that has strong data and handshake encryption. Make sure the protocol you choose has the level of advertised encryption available to it, as services typically provide more than one protocol with varying levels of encryption strength.
Optionally, depending on your use case and threat model, you may be interested in making sure Authenticated SMTP (to send email) and P2P (to file share, download, use Bitcoin, etc) are not blocked on your VPN's servers
When you start to search for services and are browsing on their websites, there are some additional items you may want to consider. Speaking of trust and privacy - some companies will use tracking cookies to determine how to best serve you ads, which other sites you've been to, and some will even phone home with specific personal information. Best case, this is an abuse of power by companies stretching the limits of their ideas on how to gather this info, worst case, it can be used to intentionally violate your privacy and tie your device back to the site and activity performed on it. Choose a company that respects your privacy enough to use few if any persistent or external tracking cookies. If they are already violating your privacy the moment you visit their site, you have no assurance that they will take your privacy seriously after hiring them to represent your interests. Available for years, https allows websites to entirely encrypt all data sent and received with the user, effectively blocking out those that might try spying on such web traffic. Choose a service that encrypts their website with an SSL Certificate. Additionally, CloudFlare, Incapsula, and similar services have recently become popular with websites for their DDoS protection and dynamic bandwidth scaling. However, these services act as an additional man in the middle between your VPN's website and you. In the wrong hands, the information they collect and have access to about your VPN's website, and your interaction with it, could be compromised. Avoid VPNs that use CloudFlare, Incapsula, and other such services.
IF YOU'RE CONCERNED WITH SECURITY
Many of the points made above are relevant to security as well as privacy, and I will point some out below.
Jurisdiction, specifically Freedom Status is important to ensure an environment where laws are enforced and physical security that we take for granted in some parts of the world are applicable to the servers we communicate with. This also helps indicate that our service and the servers we connect to are located in places that respect internet freedom. This information can be found on the Comparison Chart and confirmed on Freedom House's website.
IPv6 should be specifically tunnelled or blocked outright the same as with the privacy scenario above.
Both data and handshake encryption should be strong and available for the protocol you choose (which again, should not be PPTP). Other protocols are probably secure enough for daily use. Note that no protocol is bulletproof and exploits probably exist and are discoverable for each and every one of them. Such exploits are even more discoverable by governments with vast amounts of resources.
Read the final part on how to choose the best vpn (Restrictions, Kill switch, Warrant Canaries) soon.