I have to deal with this shit at work. It sucks. Here are the guidelines I generally follow
If it's your personal video, for your "educational purposes" only, you can use whatever song you want. Don't bother asking, it's no big deal. Give credit to the song and artist in the credits and/or in the description of the video.
Note: you cannot post an "educational purposes" video on YouTube for ad money. That's a no no. Keep in mind that YouTube scans for recognizable music and they may mess with your video even if it's you keep a low profile. Your best bet is to steer clear of YouTube all together.
For videos that you are selling or advertising, you have two options; a) use license free music (you have to pay for this, its hard to find good stuff) or b) you have to contact the artist and get their permission. Some artists are good about getting back to you, others are not. I've exchanged emails with Avicii [his manager, actually], All India Radio, RJD2, and others. At the same time, The Glitch Mob blew me off for months and I still haven't heard from them. Other artists, like Sigur Ros, have a license agreement on their website that says you can use their music under certain circumstances. No matter what you do, keep a record of your correspondence for as long as your video is online/being shown. It'll serve as your fall back if anything should change or come up.
Above all, play it safe. There's nothing worse than putting your video on YouTube only to find out 2 days later that YouTube has pulled down your audio because it came up on their meter and exceeded some artist's allowed usage.
Sparknotes: Be smart, be honest, give credit, watch out for YouTube, and lastly, stay away from EMI artists on YouTube. They're so fucking strict about their usage on YouTube its stupid.