I recently saw the documentary Cocaine Cowboys. It was mostly made up of a couple recent interviews, mixed with news footage from the 70's and 80's.

I'm curious where you obtain such footage? Directly from the news agency, or is there some archive company that has it? What do they typically charge for footage?

bbcmotiongallery.com has BBC and CBS news materials from the last 50 years. Footage can get pretty expensive and the price also depends on what licensing you need.
nbcnewsarchives.com is another site.

My message pertains to footage you've seen and would like permission to use...

Contacting the network which aired the footage is a great way to start. Generally a call to their switchboard will help, and ask for the archive division. If you can provide the subject(in the form of useful search keywords) as well as an airdate, you're more likely to get a what you're looking for.

Here's the thing. Just because they aired the footage doesn't mean they shot it or own it. Often networks will use specially recorded hits by anchors from other networks. They do sort of a bartering service sometimes(we record this for you...you record something for us when we need it) and often the originating network will hold the rights to the footage. They do this to save money. If a network you get along with and have worked with before has a reporter on scene and will give your network a satelite hit, it saves you the cost and time of sending someone down there yourself.

The archives should be able to give you details about who holds the rights for any footage they have aired.