I highly recommend, in order:
They are all awesome. Give it a listen.
I love this song:
"Destino De Abril" - The Green Car Motel Collateral Soundtrack
“Cancion Mixteca” is a beautiful song. I like this version from the ‘Paris, Texas’ - Original Motion Picture Soundtrack sung by (curiously) Harry Dean Stanton.
David Lee Roth recorded his entire “Eat 'Em and Smile” album in spanish - Sonrisa Salvaje, it’s pretty good.
“Yankee Rose”
http://www.youtube.com/watch?v=Woin2TBl4Pc
And his version of Sinatra’s “That’s Life” in spanish:
“Asi Es la Vida”
My faves:
Shakira’s album “Donde estan los Ladrones”
Mana’s “Revolucion de amor”
Juanes “Un dia normal”
I found that listening to music really helped me think in Spanish - also try reading children’s books, ramping up to books you know and like in English. The American Girls series are easy, ramping up thru Harry Potter and Ender’s Game.
All of these are good options. This question comes up once in a while, and I always dig up old threads (because I participate and they have all my music choices). 
As to what have been said, my personal faves from artists mentioned:
Shakira- Antologia and Donde estan los ladrones are her two best (IMHO). Ojos asi has good tunes, too.
Mana- IMHO, their best album yet was Cuando los angeles lloran (1994). Good mix of some serious material and some romantic material.
Jarabe de Palo- La Flaca (although I hate that song) and Depende
Mecano- Anything, really. They’re one of my “can do no wrong” bands (for me).
Juanes- Un Dia Normal
Silvio- Even more “can do no wrong” than Mecano. Yea he’s Cuban, and yea he lives in Cuba, but so what? He’s a great singer-songwriter.
In the vein of Silvio, there are Mercedes Sosa and Leon Gieco (nueva trova/folk music).
In the vein of Mecano, there is La Oreja De Van Gogh. The lead singer left the group, but their first 2-3 albums are awesome Spanish Pop, and her voice reminds me of Ana Torroja (from Mecano, she also has some good solo work).
For sexy type music, try Miguel Bose. His latest CD, Papito, is a collection of his hits, sung in duo with other artists, many of them well known in Latin America.
Others that have not been mentioned are Manu Chao (or Mano Negra), Los aterciopelados, Los Rabanes. Fast paced music includes salsa, so go check out Celia Cruz, Tito Puente, Hector Lavoe, Ruben Blades, Marc Anthony, Gilberto Santarrosa, Grupo Niche.
Ricky Martin stuff. Stop laughing and listen to his songs. His Spanish CDs are MUCH MUCH BETTER than the English pop crap. Get songs from his third solo album (A medio vivir) or his latest MTV Unplugged version, where he sings with other artists, like Mari del Chambao (also a good singer). That album also has some modernized upbeat plena (typical music from Puerto Rico).
And of course,
I second Cafe Tacuba. My lab instructor burned me a cd when I was a freshman in Spanish 202. I lost that cd, I really miss it. 
I enjoyed a lot of their songs.
Mana’s new album "Amar es Combatir"is also very good.
Similar to Mana’s style is Jaguares, however their best songs were some of their first when they were still called Caifanes.
La Quinta Estacion is another great Spanish group.
Elefante, one of my favorites, has some great spanish pop/rock.
And if you like (or at least don’t hate) mexican country Intocable is also very good.
Laura Pausini, who is Italian, also has alot of great songs in spanish but I’m sure they are just versions of her italian songs, but I find the spanish versions easier to find.
Some great but now defunct groups are La Ley, Enanitos Verdes, Soda Stereo and Heroes del Silencio (whose singer, Enrique Bunbury has some good solo stuff). All of them rock groups.
Los Enanitos Verdes are defunct? I thought they released an album a year ago or so.
And SodaStereo had a reunion tour last year (with a CD of the tour), but I’m not sure if that means they are going back to studio and reunite as a group.
In this day and age, I don’t think any group is defunct until every last member is dead and buried. This is worse than Heroes where people just won’t stay dead. Reunions are daily occurrences, no matter how bitter the fight was that killed the group.
Joaquin Sabina
Joan Manuel Serrat, listen to “Algo Personal” and “Mediterraneo” specially, the best thing about them is the Lyrics so i dont know if you’ll enjoy them at first (not understanding most of it wont help) but as you get more fluent you’ll see what i mean.
I’d recommend Orishas’ A Lo Cubano. Great Cuban urban music. Don’t panic if you don’t understand the first track, Intro, it’s not Spanish it’s Yoruba.