I've been living in Shenzhen, China, for over a year, here's my experience:
VPN: I believe a safe choice now would be www.julyrush.com. It's the one I've used the most and it works reasonably well.
The most stable protocol is usually Cisco IPSec, since it seems that it's the one with which the Great Firewall has the hardest time blocking, so try to get that working on your devices before you come. L2TP and PPTP rarely work, so don't rely on those. This is true for all VPN services I've tried, not only Julyrush.
I've tried several different VPN services during this year and none of them work very reliably all the time. They change their servers, passwords and ports, and it works fine for a while, until it gradually deteriorates up to the point where it's not very stable (as in, you get disconnected for a moment several times a day, or some servers completely stop working); then they fix it and the process starts all over again over the period of a couple months. Either way, if you just intend to browse websites that shouldn't be a problem at all.
Whatever VPN you choose, however, make sure that you subscribe to it, set it up on your phone or laptop, and test it, because you may not be able to easily access VPN websites once you're in China. Load several profiles for several different servers in case some of them do not work (I have 3 profiles on my phone and i've never had all 3 offline at the same time).
SIM: The only 3G SIM provider in China is China Unicom, that's what you should get. There's also Telecom, I think, but they're CDMA only and I'm not sure how that works. Unicom works pretty well in cities, I've heard that it has much less coverage than China Mobile and Unicom outside the larger cities, but I don't know if this is true (it's never been an issue for me).
As a backup, you could also get a China Mobile SIM card which is just 2G, but can still give you some connectivity.
My experience with the China Unicom 3G network in Shenzhen is that it's fast enough (200-500kbps up/down), but not very stable, so it can be frustrating to have a video call while moving. If you just want to connect to a VPN, browse blocked websites, upload photos and chat, that shouldn't be a problem.
On your phone, your VPN connection may drop (it always drops after a while of inactivity on my iPhone), so don't rely on your Facebook app staying connected.
Getting the card itself is easy. China Unicom seems to have the least sales points, but they're still pretty easy to find. You'll see LOTS of China Mobile shops, especially near airports and train stations. What I did was get a China Mobile card first, and use it to look up a China Unicom place on the map. There's also lots of small shops on the streets where you can easily get a card, too, and they usually have signs with the logos of the companies they work with. They may look shady but their cards work.
A few relevant comments:
Google is often blocked here. This means that it may be hard to access GMail, and any other Google services -- including Google Maps.
Maps on your phone can help you out a lot, but if you're using an Android phone, keep in mind that you may need the VPN for it to work properly. Apple's map works great and it seems to me that they're better than Google's, at least in China. On both maps you have a good chance of finding most hotels and a few restaurants (such as KFC or Pizza Hut), in English.
You should also bookmark maps.baidu.com, which is guaranteed to work, VPN or not. Keep in mind that it's all in Chinese, though.
I'm not sure of the exact legal status of VPN's, but their use is widespread, even among Chinese people; and nobody really seems to think they're doing anything illegal. When I was getting internet for my apartment, the internet company itself suggested that I should use a VPN.
If you find yourself needing to go to one of those remember to take your passport with you, they are required to request it from you before they can give you access to their computers.