It looks as if there's no direct route between Faro and Malaga. The Faro Airport website states that the only direct flights to mainland Spain are to Madrid (with Air Nostrum):
http://www.ana.pt/portal/page/portal/ANA/AEROP ORTO_FARO_CNT/?AE_FR=196131&actualmenu=184932& cboui=196131
Unless you fly via Madrid, the only other sensible alternative would seem to be to fly with TAP to Lisbon and then with either Air Nostrum or Portugalia to Malaga.
The Thomas Cook Rail Map of Europe shows that there's no rail line linking Faro into Spain. Instead, it shows that there's a bus route between Faro and Seville, from where you can link into the Spanish rail system. A bit of web-searching shows that the bus only runs twice a day, from Monday to Friday, with departures at 0920 and 1635:
http://www.damas-sa.es/buscar.htm
(Don't ask how long it takes. The operator doesn't seem to want you to know!). When you get to Seville, there are direct trains (at roughly two hourly intervals) to Malaga, with a journey time of just over two and a half hours. The train times are available on the German(!) railways website, here:
http://reiseauskunft.bahn.de/bin/query.exe/en
Chris