A cover is just a new performance of an existing released song. It's only legal to perform if you have a license. In fact, a restaurant has been sued just last year for having a band perform "Freebird" without a license.

It is understandable that people find this confusing. In the US, anyone can release recordings of covers--even without the permission of the creator of the original work--by obtaining a "mechanical license" and paying a fixed royalty. However, this doesn't apply to public performances. In other words, while without the permission of the creator you can still record a cover and sell it, you can't perform that same cover that you are legally selling publicly.

This doesn't really make any sense, but it has ended up this way because of how the copyrights for compositions and recordings were divided up when the recording industry came into existence.