After struggling with fonts in Gnuplot 4.6 (on Fedora 17) (getting the not so useful error "gdImageStringFT: Could not find/open font while printing string"), I found tonicas post on debugging the issue. Although helpful, it did not give the full solution to my problem. It turns out, many of the old fonts are not available in Fedora 17 at all.

I wanted a sans-serif font, and in the end I went for the DejaVuSans. After installing the font packages, I specifically exported that path for use with Gnuplot:

sudo yum install dejavu-sans-fonts dejavu-fonts-common
 
export GDFONTPATH=/usr/share/fonts/dejavu

Then I can use that font in Gnuplot by addressing it specifically:

set title 'Test' font 'DejaVuSans,21'