Philip - Travel IN South America is cheap, but travel TO South America is of course more expensive.
Flights to Lima, Peru are the cheapest (a few hundred bucks from Miami, DC, etc) and fairly central for adventure addicts. From Lima you can take a 8-hour bus to Hauraz or easily fly to Cusco, La Paz, Santiago, or Buenos Aires. You can sometimes find cheap flights to the latter two locations, which put you much closer to Patagonia. I have been able to find roundtrip flights from San Francisco to Santiago for around $1000.
As I write this, the current visa requirements for US citizens are:
Colombia, Ecuador, Peru - no visa fee, free stay up to 90 days
Bolivia - $140 visa fee, apply at border crossing with proper documentation, required at all border crossings, 90 out of 180 days for next five years
Chile - $140 visa fee charged only at flights arriving in Santiago (apply at airport)and valid of life of your passport, otherwise no visa is needed.
Argentina - $140 visa fee charged only at flights arriving in Buenos Aires (apply at airport)and valid of life of your passport, otherwise no visa is needed.
We found a flight for $180 (roundtrip) from Santiago to Punto Arenas, which is a few hours bus ride from Puerto Natales, the nearest big city to Torres del Paine. Los Glaciares/Fitz Roy is another bus ride of several more hours, on the Argentine side of the Andes.
Los Glaciares is free to enter at El Chalten, the town below Fitz Roy, and free to camp in the park.
As of 2010, Torres del Paine costs 14,000 pesos ($28) for the bus from Puerto Natales, plus 15,000 pesos ($30) entrance. A boat ride to the most common trailhead is 11,000 pesos($22) and camping is 4,000 pesos ($8) per person.
So, as you can see, hiking in TdP is much more expensive than Fitz Roy.
To avoid some of these costs, you can hitch-hike to the park (free!) and enter after 5pm, when the park toll booth closes (free!), camp at "unimproved" sites (free!) and don't take the boat across the lake (free!).
Hostels are about $10-12/person/night in all of the town and cities listed above. Buses are very good quality, comfortable, and rather cheap in Argentina (Chile is slightly more expensive).
OK, hope this info helps give you an idea of costs. You can find more info on the parks and our travels in Latin America on my travel blog.