One of the best ways to learn new things is by putting them to a tune. In 2nd grade I remember learning the US presidents and the state capitals by using songs and you can apply the same principal for learning languages. There are several channels on YouTube dedicated to taking Arabic songs and subtitling them with English. Here are some of my favorites:
Edit 10 February 2009: YouTube decided to ban Ethnikation's account citing copyright infringement. Her new account is Renrooni.
By far my favorite place to find subtitled Arabic songs is Ethnikation's channel. She takes requests for songs to subtitle and is great about responding to questions you post on the videos. As of right now she has over 100 songs and she is constantly adding more. I've discovered so many Arabic songs that I like that I never would have know about otherwise, plus she's pretty hot which is always a plus! Here's a recent song she uploaded called Ma Khalas ما خلاص by Samira Said.
Haifa Wehbe songs. Some of them don't have subtitles, but most of them do. Haifa is probably the most well know pop singer right now in the Arab world. Some people like her, others says she's arrogant and don't like the fact that she's had plastic surgery (عملية التجميل), but you can still use her songs to help you learn.
Nancy Ajram and has 15 of her songs subtitled on his channel. If you don't know who Nancy is, she is extremely popular in the Middle East and has a huge following. She's probably not as huge as Haifa, but the fact that she doesn't wear such revealing clothes might account for that. She's also had plastic surgery and you can see before and after pics here. Her style of music varies between love songs and pop. Clinton hasn't added any new songs for over a year, but the songs that are there are still very useful.
I like to find the lyrics written in Arabic so that I can look at them when there are words that I don't understand. Even if you see the meaning in English on the screen it's still nice to make sure you know what they're saying in Arabic. Here are some good sites for Arabic lyrics: