Does anyone know of a good (preferrably free) web page scrape program that could be used to pull headlines from the major media sources?

Is it legal to take headlines that might be copyrighted without permission? Or is only the body of the news article copyrighted?

I think just getting the headlines and then linking back to the original source should be ok.

Yes, that would probably be allowed. It wouldn't hurt to contact the soruce to just be sure.