You have to get permission from the copyright owner of the specific recording. That is almost always the record company.

The songwriter generally still owns the rights to the song (the composition), but has it managed through a publishing company. So if you want to re-record a song you generally contact the publisher, who manages the day-to-day on behalf of the artist. This should clear it up better than I can.

I remember a story where Janet Jackson went to Carly Simon directly (mutual friend I believe) and asked her if she could use one of her old songs in her new Son of a Gun recording. Carly said basically “I’ll just come to your studio and sing it for you.” So they bypassed the record company entirely because they did not use any of the existing published releases, and obviously then Carly owns the rights to her own song and she did not sell that to her publishing company.