I think you might need to contact the record label who put out the song to try to obtain permission. But I’m sure if its a popular song its going to cost you a pretty penny, especially if you are going to be using the entire song.

Although, if you are planning to not sell the app and are going to release it for free, I believe according to the Fair Use act, you would not need to obtain permission to use those songs since it would be for “learning purposes” technically. If you are worried about it however, I would consult an attorney, to ensure you are not violating any copyright laws, prior to releasing the application.

To get appropriate licensing for use of a song, find out which music publishers’ organization handles the song. The big three—ASCAP, BMI, and SESAC—have their own search engines where you can look up songs in their repertories. Once you find out which organization handles the song, approach them for licensing.

ASCAP: http://www.ascap.com/ace/
BMI: http://www.bmi.com/search
SESAC: http://www.sesac.com/repertory/terms.aspx

Sometimes the song credits will include the publisher’s name with one of these organization’s name next to it; in that case, you can spare yourself the research and approach that organization directly. (Note that different songs may have different publishers even if they’re on the same album!)

I think fair use would apply only if the app were limited to the United States, only a small portion of the song were used, and if it were used in the context of either criticism or an educational point (i.e., the fragment of the song is used to illustrates such a point). The cost (or lack of cost) of the app does not factor into whether it’s fair use or not.