The cheapest way is to buy two domestic tickets: either Paris–Hendaye and Irun–Madrid, or Paris–Cerbère and Portbou–Madrid. See below for details.
For this kind of questions, in general, Raildude is a useful resource. It is most useful in connection to Interrail, but also useful in general to get an overview of connections.
For example, for Paris–Madrid, it links six possible connections. Normally, the best connections is to take the Corail Lunéa from Paris to the Franco-Spanish border at Hendaye/Irun, then take a Spanish domestic train from there. According to Raildude, this connection is currently (2013-01-17) suspended, but it's bookable at tgv-europe.com (see below), so I'm not so sure anymore how good Raildude really is ;).
To find the cheapest option, you have two alternatives:
Either find a date that the Trenhotel direct connection is affordable. In a Super reclining seat, it might not have to be as expensive as your quote. I recall some tickets were as cheap as 70€, but I don't find any examples cheaper than the price you quoted right now. (Update 2019: this train no longer exists)
Or, probably cheaper, have separate tickets for the French and Spanish legs. This means either a French night train and a Spanish day train, or a French day train, a night at the border, and another Spanish day train. There's also a Spanish night train to Portugal that you could depart from in the middle of the night, but that's neither cheap nor comfortable.
Inside France, you can use the TGV Europe low-price calendar to find cheap connections (day or night). Try to search from Paris to Hendaye. Most days the cheapest ticket is 33€, but on some days tickets are as cheap as 17€. The cheapest ticket is either a seat on a day train, or a seat on a night train. Look carefully from what station in Paris the train departs, because night trains depart from a different station.
Inside Spain, consult www.renfe.com. Since you have already selected the date for the French part, you have less flexibility here, but my experience is anyway that ticket prices are less varying in Spain than in France. The interface is in Spanish; there is an English language interface, but it may be less complete. Renfe.com will normally only list direct trains. Click on Compra de biletes and search Irun to Madrid. Irun – Hendaye is just 5 km, and most domestic trains continue to the first station across the border, even if domestic train sites do not list this. Check a timetable to be sure. Ida means one way, Ida y vuelta means round trip. For March, I'm currently finding tickets for as little as €16.65, which would put your total train Paris–Madrid to potentially less than 35€, though more likely around 60€ since you rarely get the cheapest option for all legs.
From the comments below, you may also try Paris – Figueres and Figueres – Madrid (daytime 5 hours), or Paris – Cerbère, Port Bou – Barcelona, and Barcelona – Madrid, or, at night, directly Port Bou – Madrid. The TGV doesn't serve Cerbère or Port Bou (and is therefore not listed in the low-price calendar listed above), but can be reached by regional train from Perpignan in 30 minutes, hourly connections from Paris (check the travel-planner at Bahn.de. Then the night train Port Bou – Madrid departs 19.03, arrival Madrid 07.21. Unlike international night trains, domestic night trains in Spain are not very expensive.
One other alternative:
If you're going from Germany to Spain and back all the way by train, you might want to consider to get an Interrail Global Pass. You'll need to buy a 50%-ticket to and from the border of your own country, but after that you only need reservations. Particularly if you're in the youth category (below 26 years old) that might very well lead to a cheaper journey, with the big advantage that your tickets are flexible, and can be rebooked at (almost) no financial cost. Rebooking however can involve long queues at railway stations, particularly in France...
