Minibuses or shared Jeeps leave the transport terminal of Neiva. The trip lasts 1 hour and costs 5,000 COP. There's no point to stay in Villavieja though. Just stay in the minibus until it takes you right into the desert. It should be able to drop you off directly at a hostel.
The collectivos from Neiva to Villavieja charge 6,000 COP per person and 15,000 if they bring you directly to the desert (more for a single person, less for a group). A single traveler might just get off at Villavieja and find a mototaxi (motorbike) to the desert for 10,000 COP or less.
You can leave buses coming from Medellín and Bogota in a village called Aipe just next to Villaviaje. A motorcycle and a canoe to cross the river Magdalena cost about 7000. Don't forget to haggle! Alternatively, you can walk to the river (about 20 min) and just pay the crossing for 3,000 COP (09/18). You can also reenter buses going to Medellín or Bogota in Aipe (at the highway) and thus save some time.
Getting around the city should not be a problem as it's small enough to be covered on foot. The tricky part is getting around the desert as there is no public transportation and it can get expensive. You can either :
Everyone seems to offer morning or evening tours of the desert for 40,000 pesos per person. It is a bit overpriced for what you get. You can do it by yourself. It is safe.
Rent a bicycle for 5,000 COP or less an hour and go for a ride to Los Hoyos. In September 2018 the shop next to Camping El Cusco rented bikes for 15,000 for 5h.
Villavieja is a nice colombian town and really authentic. The Hospedaje Villa Rocio is a great deal. You get a super clean and huge room for up to 3-4 people. From 30 to 50.000 COL depent if you like van or aircon. Coffee included, a fridge and 24 h electricity! Your choice. Walk into the dessert around 1 h to 1,5 h.
In the Desert
There's absolutely no point to stay in Villavieja. There are a number of options in the desert that are well priced (for example 15,000 COP per person for a room, or 10,000 COP for a hammock - July 2015). Mid week there's no need to book. Accommodation is basic and electricity is only available during the evening, however it is beautiful in the desert and the temperature is in fact quite pleasant. Just make sure your camera and phone are charged before you come. Expect to pay COP 5,000 for breakfast of COP 10,000 for lunch or dinner.
Hostal Noches del Saturno seems to be popular but the staff is not friendly and the food is not good. Dona Lilia (the closest to the observatory) has the best food and is a good place to stay. There are more accommodation options. All of them are basic with solar light to charge phones. Expect to pay 10,000 COP for a hammock (5,000 if you bring your own hammock or tent) and more for a cabana. (Dec 2015)
La Tranquilidad is another solid option with hammocks, dorm rooms, tents & private room available. It also does food which is a big plus point. Prices are pretty much the same for whichever place you chose but I was recommended this place by a hostel in San Augustin and for me was a good choice. They also have motorcycles you can rent which is a great way to explore the desert as well as tours on horses. (Jan 2017)
If you have a tent, you might want to check out Camping El Cusco. There you can pitch your tent just on the edge of the labyrinth with a beautiful view over the red desert. They can also arrange transportation back to Villavieja on motorbikes for 7,000 pp. Camping is 7,000 pp/on. (Sep 2018)