Requirements for adding outdoor outlets
You can use most types of conduit outdoors, though some will require liquidtight fittings. Cost wise, and due to the ease of use, I'd recommend schedule 80 PVC conduit. 

schedule 80 PVC conduit http://static.hardwarestore.com/media/product/636554_front500.jpg

As long as you use the proper size conduit and boxes, you can indeed run all the circuits through the same conduit.  

If you used 14 AWG THWN conductors (15 ampere circuit), you could jam them into 1/2" schedule 80 PVC conduit. If you want a bit easier pull, you could use 3/4" schedule 80 PVC conduit.  If you're using 12 AWG THWN conductors (20 ampere circuit), you'll have to use 3/4" schedule 80 PVC conduit. I figured for 3 conductors per circuit (hot, neutral, ground), so that's 9 total.

If the circuit is GFCI protected, you can install the conduit 12" underground. If it's not, you'll have to go 18" deep. Since you're installing outdoor outlets, you'll have to GFCI protect them anyway. If you use a GFCI breaker, you can provide that protection, and save yourself some digging.

Wherever you go in or out of the ground, you'll want to install an expansion fitting.