I don't know if graphic headlines convert better or not, but for the reasons Stephen mentioned I think I'd stick with plain old text headlines myself - but like everything you'd really need to test to see what works best in your case. Graphics might convert better, but I would certainly think that'd affect your
SEO so it might not be worth the tradeoff.
As far as graphic programs go, Photoshop is what I prefer, but the price tag is steep and the learning cure can be too. I think they still make an entry level program (Photoshop elements) that may be a better choice for you, and I'd also recommend you look into Paint Shop Pro (inexpensive) and
http://www.gimp.org/ which is free.
Steve
P.S. Fireworks is a nice program too - but I think your second most expensive option next to photoshop.