When in doubt, ask permission.
Scratch that. Even when not in doubt, ask permission. And get it in writing.

I worked on a (ultimately cancelled) quiz type game. The bulk of my time was spent securing the rights for sound clips and content.

Short answer is that there is no minimum amount of song you can play without needing permission/license from the copyright holder.
Here's a bit of a blurb on "fair use" from the government copyright site.

"There is no specific number of words, lines, or notes that may safely be taken without permission."
Source: http://www.copyright.gov/fls/fl102.html

Brian
Register for GameSoundCon 2012 San Francisco
Oct 24/25
www.GameSoundCon.com

For music, you need to contact the music publisher (who owns the abstract entity which is "the song") as well as whoever owns the recording itself. Often, they're the same legal entity, but not always.
Licensing varies tremendously... If you're doing a "Guns and Roses Trivia Game" then GNR will likely charge you an arm and a leg. if you have 4 seconds of one GNR song as the answer to one question out of 3,000, they'll be more accommodating.

There are companies that all they do is negotiate rights between all the relevant players. it's often messy and always tricky and the rights owners are sometimes all over the map (literally).
Games like these may be a cakewalk from a programming perspective, but from a legal perspective, they can be a ton of work.

Brian
Registration now open for GameSoundCon 2012
October 24-25, San Francisco, CA