Find Legal Music to Use in a Podcast or Video

How to use music creatively without going to jail or getting fined.

Steps

Determine what kind of music you need. Every project is different, requiring different kinds of music. Ask yourself what you are trying to accomplish with your soundtrack.
Consider music that is licensed under Creative Commons: There are many sources of CC content and most are pretty proud of the fact that they are part part of the Creative Commons movement. Include creative commons in your web search. Check out http://creativecommons.org/ and learn more about your rights and responsibilities for using CC content.
Figure out where to find it: There are a lot of good sources for "production music" I'll reference a few later. But maybe you just have to use a piece by your favorite band. That brings us to the next step.
Know your rights. In most cases you do not have the right to pull a song from your favorite CD and use it in your creative work (even if it's just for "personal" use). With the recent increase in strict enforcement of copyright law it's important to make sure your up to date on what you can and can't do. Look at Jamendo.
Get worry free music. There are lots of musicians and composers out there making original music which they can give you the rights to use. Some companies exist just for this purpose; see below.

If you are starting to feel overwhelmed by this process, you may want to consider music that is designed specifically for production work. The most economical route is typically going to be Royalty Free Music. When you purchase a royalty free licensed track, you don't have to pay ongoing royalties or synchronization fees. I'll list some of my favorite Royalty Free companies below. But be careful. Not all royalty free licenses are the same. Some of the license agreement change if your project has a "major distribution". So read the fine print, and keep a copy of the license agreement in our files.
Just because an original work is in the public domain, does not mean that a more current arraignment, performance, or recording is public domain. Also, if your project has an international market, make sure you understand the laws outside of the US. The copyright law abroad does not always recognize the American standard for "public domain."
You can obtain license to music you wish to use (that isn't your own property) ...But it won't be cheap, and unfortunately, the "big guys" are not often interested in working out a license deal for a "small production". You will find that some of the smaller companies will work with you (with very reasonable prices). Just make sure you are getting *all* the licenses you need. These may include (but are not limited to) synchronization, mechanical, master-use.

Copyright laws are constantly changing. Hopefully these resources will be a helpful starting point -- they should not be a definitive source of legal advice.