Technically, if you are copying, editing, synching, exhibiting, distributing, reproducing the music not for your own personal use, you are breaking the law and open to prosecution. Realistically, if you're making a small video, no one's likely to notice. They're too busy suing the pants off of file sharing websites. That said, I have heard of cases where people have received cease and desist letters.
How do you be 'legit'? You need three licenses--mechanical reproduction license,
synching license, master use license. And then you have to make sure that each of those specifically covers the way in which you will be using the music. For example, some licenses allow you to make DVDs, but not publish on the internet.
Don't have a lawyer? You can download some releases here:
http://www.current.tv/make/resources
Obviously, you'd need to rework them for your own company and purposes.
Hope that helps.