Music Rights... I think???

#1 You'll need to contact the whoever holds the rights, which may or may not be the original creator, to the song and work out a licensing agreement with them.

#2 IIRC, as long as you make the legally-required royalty payments, you don't need anyone's permission. A "compulsory license" was established a long time ago to prevent monopolistic behavior by publishers. Radio or TV stations, for example, don't need to get permission before broadcasting a song or show; they simply keep track of what they've played, and make the appropriate royalty payments.

I'm not a lawyer though! You should do some studying at the Copyright Office, and talk to a lawyer who's familiar with copyright.

#3 The Requiem for a Dream music has been used a wee bit too much over the years ;)

Music licensing is a bit of a mess. There are separate contracts for using music in a game, movie, TV show, commercial, radio or a public place in the worst cases. Here's an example of a cheap place:
www.shockwave-sound.com/

Cheap being 30 dollars for most purposes per tune.

Clint Mansell, who made the Requiem for a Dream music, is probably in a higher price range:
www.clintmansell.com/

Can't hurt to ask him directly how to licence his tracks for game purposes. He's probably got a company handling it for him.

#4 As Ronny points out, there are loads of great, unknown, cheap composers knocking out really good music for a license which won't cost the earth.
www.audiojungle.net
www.neosounds.com
www.sfxsource.com

Also check the various blogs and resources which get advertised/spammed on this sort of thing.

Though if you do find out how to license this big-budget stuff and how much it costs, do tell the rest of us.

#5 @Sherman
You are required to have both synchronization (to sync music to a video component) as well as general usage rights licensing. Often the usage and synchronization licenses are owned by different entities. The cases you are noting are special use cases for specific types of organizations, similar to the rights that libraries have with the publishing industry. I wish it were as simple as you noted for indie filmmakers. It would have made my life a *lot* easier. Of course, I wouldn't have contracted some excellent composers or worked with a number of indie artists that I otherwise would have missed hearing.

#6 Cool, thanks guys, you've all helped clarify things for me :D