(Someone please correct me if I'm wrong)
I thought in the US, when playing songs live (or DJing) the licensing fees are the responsibility of the venue, not the performer. The venue pays a fee to BMI or ASCAP, and that gives performers the right to play any song they want, including covers. Even if a bar does a karaoke night, they still have to pay the fee. A bar near me actually got sued because they weren't paying their fee, which caused them to shut down. One of the only music venues in the state, too ;_;
This only applies to live performances, though. If you're recording a song and selling it, what everyone else said applies.