Trains from Madrid to Malaga leave from the Atocha RENFE station at the southern end of Paseo del Prado. From the airport you can take the Metro, the Aerocity Van or you can take a taxi. In a previous post I noted that I went from the airport to Atocha with two friends and we had to take two taxis. One driver charged 2,200 pesetas and the other charged 4,000 pesetas for the 20 minute ride.

MadridMan's Local Treansportation Link gives you info on RENFE. You can check the Timetables and Prices for the dates you are going to be traveling. There is sometimes a train at 8:20 pm that takes 4 hours to Malaga. This train is only scheduled on Mondays, Tuesdays, Fridays and Sundays. The one way fare on this train is 7100 pesetas. There is a discount on a roundtrip fare.