After a hundred years give or take LOL copy right will expire and songs become public domain. So, they have to be super old.
If you can find the songs here
http://www.harryfox.com/index.jsp
You should be able to easily acquire licenses to record and sell. They say even if you're not selling it you still need licensing, but most people don't get them for cover songs. You'll only need mechanical licenses if you're going to have actual media printed like CDs, Records etc. If not and it will be digitally distributed you'll want digital licenses.
That's how I understand it at least. I may be off a tiny bit, but all the info you need will be on that website above.