Puerto Madryn is a city in Argentina in the province of Chubut. It's still in Argentinian Patagonia and located on the famous Ruta 3 that leads from Argentina's deep south along the Atlantic coast north towards Buenos Aires via Bahia Blanca, Comodoro Rivadavia, Rio Gallegos and even Ushuaia, even though that crosses into Chile and back. Puerto Madryn is the closest city to the Peninsula Valdes.
North towards Bahia Blanca, Buenos Aires
Head back to the Ruta 3 via the airport. From the entrance to the airport it's a 1,5 kilometer walk to the YPF on the Ruta 3. That YPF is on the wrong side of the road, but will work for traffic in all directions. In Patagonia, asking people directly works better than waiting with a thumb and/or sign.
South towards Trelew, Rawson, Comodoro Rivadavia, Rio Gallegos and Ushuaia
Same as north, but ask for a ride south at that gas station. The Ruta 3 will turn from a casual road into a two-lane highway for the short stretch to Trelew.
North East towards Puerto Piramides on the natural reserve Peninsula Valdes
To get here, leave Puerto Madryn northward on the Ruta 1. A colectivo goes to and beyond the outer town roundabout, from which you can catch a ride on the Ruta 1 either till the crossing with the Ruta 42, or with the more common crossing with the Ruta 2. From there, the sparse traffic will take you to Puerto Piramides on the peninsula.
This peninsula - officially written as "Península Valdés" - is a giant natural reserve with the only real settlement being Puerto Pirámides. There's an entrance fee of a couple of hundred pesos (yikes!), but Mind of a Hitchhiker got in for free by hitchhiking with an inhabitant of the town and both lying about being friends for a long time to the natural reserve people. That was the driver's idea and it worked. Explore the island and its seal, walrus and potential whale population. You can hitchhike around to the lighthouse, but out of season there's not many people going there picking up hitchhikers. In summer, the town is apparently a surfing and hippie town, with many artisans trekking here to enjoy the god-awesome nature.
At the northern most crossing into Puerto Madryn on the Ruta 3, there's an YPF gas station. When Mind of a Hitchhiker got dropped off there late at night, she got offered a ride into town with the YPF employee's minivan during a shift change.
Accommodation and Sleep
The kind people of said YPF on the Ruta 3 don't particularly mind if you nap inside away from the cold winter wind.