99% of the time if you use it for free permission is not needed, if you make any cash off of it then you better get permission before you get sued... if it's used for free then chances are like stated before they'll just look at it as free publicity...

Usually if you get ahold of the record company that the band is on that you plan on using the song of they will do what is needed to get you the permission to use the song, or spoof the song. It's a long process though.