West towards Valladolid, Mérida
Take the city bus to Ruta 43 (from the ADO bus station), ask the driver to be sure he's going towards la "carretera a Valladolid". When you'll go a little bit out of the city, you'll see a gas station, and not far down the same direction another one. Asking for a ride in either one of them should be easy.
Walk 10 minutes West and there's a speedbump (tope). Thumbing there is also possible.
Update 2018: The highway that is going towards Merida is called Avenida Lopez Portillo. The colectivos that go there are stopping in front of Mc Donalds at Avenida Tulum, on the opposite site of the ADO terminal. You can take any colectivo that has PORTILLO written on the windows (10 mx). Get as far as you can by colectivo and find a ride at one of the many speed bumps.
Places to avoid
Most likely the hotel zone or Cancún in general if you're not up to crowdy beach vacation at all-inclusive resort hotels.
Accommodation and Sleep
You could definitely sleep in the airport if you're into such kinds of places.
Other useful info
Isla de mujeres Is an 18min boat ride from Cancun. Although it's touristy, it is well worth a visit. There used to be a cheaper ferry only for cars, but they don't take pedestrians anymore, so Ultramar Is the only option. Tourist price is 150pesos one way (it's a black ticket), but if you kindly ask an islander to buy the ticket for you the price would be 42pesos (orange colour ticket), or a Quintana Roo resident (purple colour ticket) it would be 78pesos. Hitchhiking within the island is very easy, make sure to visit the Southern point as well.