If you want to license for downloads (at ~9c a download), this site makes it easy, though they charge a significant overhead: https://www.songclearance.com/
If you want to do some more footwork, you can dig up the info you need and mail notices/cheques to the copyright holders yourself, and save that overhead.
If you want to license for video (e.g. YouTube), you need to actually talk to them and make a deal. In the majority of cases this is impossible.
As said already in this thread, though, in practice if you put up an unlicensed cover it will almost always be unnoticed/ignored/tolerated/accepted by the copyright holder. The cases where people do get sued usually involve a moneymaking situation. I'm saying these are tendencies, but if you're not going to license you will be taking a risk (they can still sue you even if you didn't charge for it, if they want).
In my own experience, I've covered some notable things, and I pay the mechanical licensing for downloads that I sell. I also put them on youtube, and all that happened was the owners flagged it as theirs and put ads on my video so they'd make revenue on it. (Either that or they've been ignored, or just flagged as theirs but not taken down.)