It is a largely touristic city. While not so extensive as the capital Mexico City, it is still easier to catch a bus or shared taxi out to the highways to hitchhike. Close to Oaxaca is the archaelogical site of Monte Albán. A little bit further away is Mitla, another archaeological site, as well as the natural site of Hierve el Agua.
North towards Puebla, Mexico City
Go to the central bus terminal (abastos), from there look for a bus or shared taxi that is heading for Etla, and ask them to drop you off at the entrance to the Highway 135D (they also call it la supercaretera), it shouldn't cost more than 10 or 15 pesos per person. From where the bus drops you you will have to walk about 5 minutes up the slip way. A little way down the highway there's a tree (for shade) and you can hitch from there. Traffic moves pretty quickly, so a sign is advisable, but there's a comfortable shoulder and good visibility. If you're having trouble getting a ride, try writing "caseta" (tollbooth) -- there's a tollbooth a good few minutes down the road (driving), and pretty much every vehicle going by should be going at least that far.
South towards San Jose del Pacífico, Puerto Escondido
You can try hitching straight out of town on Avenida Símbolos Patrios. To get a head start, though, for around 10 pesos you can catch a shared taxi to San Bartolomo or, even better, to Vincente Guerrero. These (wine red coloured) share taxis can be found heading down Avenida símbolos patrios. From Vincente Guerrero, walk to the Y (pronounced y-griega, Y junction) or ask the share taxi driver to drop you there. Traffic will be heading to Ocotlán, Miahuatlán, San José, and the coast. If traffic gets a bit thin after Miahuatlán, a shared pickup truck taxi from there to San Jose will cost you around 30 pesos. The road is beautiful, but known to induce car-sickness if you're going faster than 20 km/h.
Again it's recommended to take public transport out of the city. Colectivos leave from near the bus terminal/baseball stadium. You might be tempted to only go as far as Sta. Maria del Tule, but the price is the same if you go to Tlacolula or even as far as to Mitla. If you go to Mitla, you can get dropped off at the crossroads with the autopista that's under construction, and hitch at the roundabout there. If you're headed to Chiapas, be aware that the spot where hwy 190 hits the autopista a couple of kilometers before Tehuantepec is really desolate -- there's no shade, no water, and very little traffic. Zenit was seriously recommended to hitch through Tehuantepec and Juchitán, supposedly the way most people drive, and was very close to doing this when he caught a fairly lucky ride to Santo Domingo.