Very true, you do have to pay for using the song, if not you can be charged for copyright infringement. But what most people dont realize is that once a song has been used or should I say released on a album, the artist cannot deny you usage of the song. You will be required to pay what is called the "statutory rate" for using the song. It would be great to get the permission and blessing of the actual writer of the song but once a song is released on a album it is available to the world, for a fee of course.
Now if the song has never been performed of if your the first artist to use a writers material they have the right to charge you whatever for first usage of the song.
Just some info, I hope you find it useful.