To reproduce a song (that is, to "cover it") in audio format, one needs a mechanical license ("mechanical" licenses get their origins from the days of player piano rolls, so I hope that is a good way for you to remember it). This mechanical license grants a cover artist the right to play the song and even charge money for it (but not to sample the original recording, or use the original recording in any way...they have to re-record all the parts themselves).
In the United States, mechanical licenses are compulsory with a statutory royalty rate. What that means is that as long as you're performing a cover (not a remix, sample, interpolation, etc.,), and as long as you pay the legally mandated royalty rate to the copyright owner, the copyright owner must grant the mechanical license.
So, what a group like Walk Off the Earth does is they work with some organization like Loudr or Harry Fox Agency. Loudr, Harry Fox Agency, etc., will contact the appropriate music publisher, send them a notice of intent that Walk off the earth plans to cover their song, and then Loudr makes sure that the appropriate royalty goes to the publisher.
OK. So everything I just wrote above only applies to the AUDIO.
If you want to synchronize that audio with visual (e.g., for a youtube music video), then you need an additional license called a synch license. Synch licenses aren't compulsory -- so copyright owners don't HAVE to give them, and there is no federally mandated royalty rate for them. So, normally, you'd have to work with the music publisher/copyright owner on a case-by-case basis.
HOWEVER, YouTube has negotiated terms that satisfy the royalty requirements with many (but not all) copyright owners -- this is the content ID system. If a person uploads a qualifying cover to YouTube and it is registered in content ID, then content ID should automatically match the song. The YouTuber then has an option to check that this is a cover, in which case, there can be revenue sharing between the YouTuber and the original copyright holder.
There is a page on YouTube called "Music Policies" where you can see what songs are in content ID, and what the copyright holders' policies are. (For example, some don't allow covers, so Music Policies will instead say that your video might be muted or might be blocked in some or all countries.)