You have just asked a big question with a big answer. If you have any plans to sell a recording of this, yes, you need permission. First, you need to find out if the song is registered for mechanical royalties, usually with BMI or ASCAP.
Then you have 3 ways you can go-
1. Ignore it all, and hope you don't make any real money. The potential liability would be $500,000 for each album it's on (not each copy). Most likely, if you don't have deep pockets, nobody will ever come after you. You'll just be a petty, song stealing, bottom feeding thief.
2. Contact the suits (legal staff or executive producer) at whatever label (most likely) who have the copyrights and beg them to let you do an adaptation of the song for free or cheap. Explain that you are nobody, and are just trying to do the right thing. They might be kind, but whatever deal you work out, if any, it doesn't count for diddly unless you have it in writing. If they are in a good mood, they might just let you do it. Or- they can try to shake you down for any amount of money they think they can wring out of you, and can prevent you from doing the song. or actually go after you for that $500,000 or a portion of it,if you release it, if they are bored, and their lawyers have nothing better to do.
Please note- your problem is this- You aren't recording their song, that would be much easier. You are trying to publish a derivative work, that is, an adaptation of their artistic property. If you were just covering the song, you would contact the Harry Fox Agency, the lawyers who process mechanical royalties for ASCAP and BMI. They are called mechanical royalties, because you don't need their permission, you just have to pay. It changes from year to year, but last I knew it was $.08 per copy, with a minimum license for 500 copies. That's $40.00 and all the paperwork pain in the ass you can stand, if the arrogant suits will even talk to you. They will if you are persistent. In the rare case that the song is not registered to ASCAP or BMI, you can just pay the mechanicals to whoever owns the copyright.
The problem is that derivative works or adaptations are not subject to mechanical license. You *have* to have the written permission of the copyright holder to do a derivative work.
3. Rewrite the damn song, until it does not rise to the level of a copyright infringement. Just do it.
I can tell you all of this because my album, "Reunion", which I produced, has one song that could be argued, I believe in error, to be derivative, and one cover, as well as some co-written pieces. Always remember- titles and "short phrases" are not copyrightable. It's up to a jury to decide if they can tell your work is derived. Thank God for my wife, the executive producer of this puppy, who figured a lot of this out. And we did pay the mechanicals on Ira Gershwin's "Summertime", and duly copyrighted the whole mess. What a monumental pain in the ass. But it was a learning experience. Now we know how to handle it going forward, as we begin to release other people's stuff on our label. Yay.-Richie