It comes with practice, there is no magical formula, unfortunately. Words in songs are spoken with different accents, and the intonation is not natural. For example if you have been taught UK English, you might struggle more with Americal songs. The other problem is that songs often use slang, which is hard to understand if you are a foreigner. Finally, believe it or not, but when I began to understand the lyrics of my favourite songs, it really put me off because the meaning is nothing like I expected.

Native speakers don't understand lyrics either. Relevant webcomic the other day: http://xkcd.com/1538/

It depends on what kind of music you like to listen to, but song lyrics can be hard to understand even for native speakers. I would say pick an artist that you like and whose songs you understand a little better than most, and then listen to a bunch of their songs. Once you get used to the way that artist pronounces things, it will become easier and easier to understand what that person is saying. If you repeat this for a few artists, you'll improve dramatically. You can also watch youtube videos that show the lyrics. Hope that helps!