You don't need a C wire for the Nest, although if you have one it's recommended to use it. The Nest has a small internal battery and can trickle-charge from the R and W wires.
As others have mentioned, there can be issues with running without a C wire. Their "power stealing" technique did not seem to be effective for keeping my first-generation Nest from running out of battery. (Although there may be some variables in my situation that contribute to the problem.) I blogged about it here: http://cafbit.com/entry/nest_learning_thermostat
If you dive into the details there's a ton of disclaimers, limitations, and gotchas running without the C wire. See [0] amongst others. As I said above, I do not recommend.
Just because you CAN do something doesn't mean you SHOULD. This is definitely one of those cases. If you want your Nest to be running problem free on most systems (or any other smart thermostat for that matter), just assume you need the C.
They say it's only "recommended", but my furnace was short cycling without it and required me to run a C wire to it. I'd say that it's pretty much mandatory for a modern furnace.
I've been running mine for a few months without the C wire, but I've definitely had the occasional bit of odd behaviour from it (eg, dead battery), that I believe will be resolved when I get around to running it some 18/5.