Calimike, tell us where you are flying in to and out of. That way we can give you better suggestions. Look into an open-jaw ticket, which is flying into one city and out of another. Often, it is no more expensive than a regular ticket. (Unfortunately it is usually more for Sevilla).

Alfavela: You can take a bus Barcelona - Bilbao (or Santander). I took one Santander to Barcelona in July. I wouldn't recommend the 'tren internacional' between Vigo and Porto. It's very slow. I would recommend the Alfa: Porto - Lisboa. There's also an Iberia-pass (includes Portugal) but you won't find any train line from the Algarve to Huelva. Busing it might be your best bet.

If I might join this conversation with another question. I am going from Madrid to Santiago, and would like to know if it si better to fly or to take the train. Then I am taking the train from Santiago de Compostela to Fatima, Portugal, to Salamanca and back to Madrid. Any advice on trains to stay away from?
Gracias

Its usually less expensive to purchase airline tickets between cities once you are in Spain, alfavela. I'm sure Antonio or one of our other Spanish members can confirm this.
If you are planning on trains and/or buses - get your tickets a day or two before if between major cities - if between smaller ones, you can pick tickets up prior to departure with no hassles.