From my research:
If you are going to sell a cover, in any form, you must license it.
If you are going to perform a cover at a gig or something, the artist already gets paid for it.
If, however, you are making money on the gig you perform the cover, technically, you have to pay for the license, but unless a rep from the artist is there, you don't have anything to worry about, really.
If you are just recording a cover to give out to some of your friends, or for school, or just playing a song on a street corner, you do not have to pay for it.
Really, the defining quality is if you are going to make money off it.