How do I pick a VPN provider?

First you should ask your self: What advantage does a VPN provider have over providing your own with something like OpenVPN? If you are paranoid you could get a Virtual private Server(VPS) host. Other than that I would make sure that the service was fast, cheap and wasn't in the news for a security breach.

If you are concerned about government eavesdropping, then you might take national privacy laws and the political situation into consideration, i.e. choose VPN providers unlikely to cooperate with local authorities. Cablegate revealed that some countries cooperated with the U.S. more than others, for example. Sweden played lapdog. Austria annoyed the U.S. etc.

As an aside, you should consider using HTTPS Everywhere whether using a VPN or not. HTTPS Everywhere has become the default in the Tor Browser Bundle.

I'd definitely pick foreign VPN and make sure that they have a clear zero log policy.

Her's an interesting read:

http://torrentfreak.com/which-vpn-providers-really-take-anonymity-seriously-111007/