As far as hiding IP address goes:
Tor does provide a decent level of anonymity but creates its own set of problems, in particular Tor users are a frequent target for traffic sniffing and man-in-the-middle attacks due to compromised exit nodes (see How much can I trust Tor?), so I don't recommend it.
Instead of Tor you can use I2P, which does not suffer this vulnerability because it uses a predefined exit node (or the one you manually choose), and the exit nodes are usually well-maintained servers, so they're way less likely to be malicious or compromised.
VPN is easily tracked down by traffic analysis - tracking packet sizes, network lag and timings, etc. Tor is more resilient to that, and I2P is supposed to be even more resilient but it was not yet investigated as thoroughly as Tor was. Cryptohippie VPN also takes traffic analysis into account and adds additional layers of protection against it.
However, obscuring traffic origin is just a part of the problem.
VPNs and anonymity networks do not (and usually can not) do anything about your browser fingerprint. You can reduce tracking, but not defeat tracking.
Here's one simple scenario to consider. Every time you browse the web without an anonymity network, the browser fingerprint is sent out there from your real IP. The fingerprint-IP pair can be recorded. If you browse the web with an anonymity network later, your browser fingerprint stays the same - others can still recognize you. Moreover, they may have your real IP address recorded. You're no longer anonymous.
It's enough to go online without an anonymity network just once to blow your cover, both in the past and future, forever (until you significantly change your software setup).
So remember you're being tracked, and NEVER EVER use the same web browser with and without an anonymity network.
In fact, this is not limited to web browsers. Other applications may have a fingerprint too (e.g. BitTorrent clients do), but they are not researched as thoroughly as web browsers were. If you're going to use an application via an anonymity network, be cautious about its setup and make sure it goes into the anonymity network right away, without contacting with the "non-anonymous" Internet even once. Otherwise your attempts at anonymity are in vain.
To avoid disclosing your IP by fingerprinting and not bother remembering which app should be anonymous and which should not (while every mistake is grave), I recommend running anonymity-oriented Linux distros, like Tails or Liberté. This way you'll be sure which programs are anonymous and which are not, and they won't be able to leak their fingerprints into the "non-anonymous" Internet because these distros explicitly prohibit any non-anonymous communications. It's possible to run them in a VM, but better do on a dedicated machine to avoid hardware-based fingerpriting and use better random number generators.
Finally, tracking may be not application- or instance-specific; user accounts on websites uniquely identify you (duh). If you want to stay anonymous, you have to access your user accounts via an anonymity network either always or never. The easiest way to do this is to establish a different identity for anonymous browsing.
Control your data online
Remember, you are tracked. You can reduce tracking, but not defeat tracking. And you leave a lot of info about yourself as you browse, from what your interests are to what places you visit to where you live. For example, search engine history tells a lot about you and sometimes can uniquely identify you. Some other websites collect A LOT of info about you or force you to disclose it, and what's worse, they often disclose it to third parties.
For a start, use an anonymous search engine: ixquick, startpage.com (anonymous Google with slightly outdated data), DuckDuckGo or run a local seeks instance to be sure. There are some search engines available inside I2P network too.
Social networks are evil. You can either not use them altogether or own your data by using Diaspora.
Online map services are not necessarily evil, but they get important info about you. I'm not aware of any anonymous map services, but of course I recommend avoiding Google Maps. Perhaps OpenStreetMap tracks less or doesn't track, but I haven't checked.
Same goes for email, IM, etc. Communicate via SSL'd and non-logged email and IM or use end-to-end encryption via a web of trust.
Finally, try to reduce tracking. Use a browser that supports DoNotTrack HTTP header and enable DoNotTrack headers in settings. Use some tracking-blocker browser extension. Use Mozilla Collusion to analyze and disable tracking. Use DNSCrypt if you don't want your ISP to know which websites you visit, or at least don't forget to check for DNS leaks if you're trying to use a custom DNS server without encryption. Remember you're being tracked at all times, no matter what you do to get rid of it. Read privacy policies. Be paranoid.