Обсуждение статьи тематического каталога: Русские буквы в EPS из gnuplot и LaTeX (rus gnuplot image graph font charset latex tex postscript eps)Ссылка на текст статьи: http://www.opennet.me/base/rus/gnuplot_rus.txt.html
установить cm-super (apt-get install cm-super)\usepackage[T1]{fontenc}