"For a small production, even getting a one-hit wonder's songs can be taxing, but it is not out of the question. It is just a matter of contacting the right people and trying to get on the same wavelength. If a film is really low-budget, there is probably a reason, and you probably have very little money to spend on acquiring music rights, but a little money can go a long way if you have a lot of grit and some decent bargaining skills.
To secure the rights to a particular recording of a song, a filmmaker must have both a Master license and a Synchronization license. A master license is obtained through the record label, or whoever owns the copyright to the recording you want to use. It will usually be the record label, though some very wealthy artists, such as Madonna, have the money to buy back their catalog, and therefore own all of their own material.
A synchronization license is obtained through the song publisher, or the copyright owner of the actual musical composition. It will usually be a publishing company that owns the composition copyright, but again, in certain instances, an artist may have all rights to their songs. If you want to use a master recording, a recording from an artist on a label, you must get both of these licenses for the usage to be legal.
If you just want to use the song's composition, and will have the music and lyrics re-recorded for your production, you will need only the rights to the song itself, which means you need only the synchronization license. Don't just assume it will be cheaper to re-record the song though. Depending on the deal you get with the label, and factoring in the cost of studio rental and payment of musicians, you may be better off just shelling out the dough for the master recording.
The lower on the totem pole a person is, the more likely you will be able to get their music at a reasonable cost.
What I did was contact both the record label and the music publisher for the song that I wanted and I asked for free festival rights. Both of them responded to me rather quickly. The music publisher granted me the rights to use the song in the movie in festival for free with a MFN, or Most Favored Nations, clause. The MFN clause means that if someone else gets paid then they have to get paid the same amount. The record label told me that I could have the rights from them for $350. If I accepted this, then I would also have to pay the publisher $350 due to the MFN clause. That was way more that we could afford, so I counter offered to the record label with an offer of $75. A few weeks later I heard back from them and they had accepted my offer! I now had to pay the publisher $75 as well, but I got the full rights for only $150!"
----------------------------------
another (much easier) option for getting the rights for using artist's music is going to a site like
http://magnatune.com/info/licensing
They have a giant catalogue of all types of music and indie bands and artists who have submitted their recordings just for this purpose. Once you find a song you like, you can set parameters for the type of project and your budget and they will quote how much you'll have to pay.