うちでは emacs-20.7 ですし、plus パッチを当てたものは、
それとは別なマシンに入れたので、問題を確認することがで
きなくてまともなフォローができませんが、

mario> Emacs 21.3 + gnuplot-mode 0.6.0 ではうまくいきません(core dump)。

1) core dump して落ちるのは gnuplot ですか、Emacs ですか。
2) 同じ設定で gnuplot-3.8k.3+0.10 (等の古いもの) ではどう
ですか。
3) title 等で日本語を書いたときだけ落ちるのですか。

うちの emacs-20.7 (正確には emcws-20.7) + gnuplot-3.8k.3+0.10
+ gnuplot-mode-0.6.0 では、提示されていた設定で

set title "テスト"
plot sin(x)

では特に問題はありませんでした。

ちなみに、私は普段は

(set-language-environment "Japanese")
(prefer-coding-system 'euc-japan-unix)
(set-terminal-coding-system 'euc-jp)
(set-keyboard-coding-system 'euc-jp)
;;(set-buffer-file-coding-system 'euc-jp)
;;(setq default-buffer-file-coding-system 'euc-jp)

な設定にしています (process-coding-system は変更無し)。
Emacs 21.X は知りませんので外していたらすみません。

〔ツリー構成〕

【259】 X11での日本語ラベル 2004/7/30(金)09:55 mario (144) ≪

┣【261】 re(1):X11での日本語ラベル 2004/7/30(金)12:14 竹の (426)

┣【262】 re(2):X11での日本語ラベル 2004/7/30(金)21:48 竹の (413)

┣【264】 re(3):X11での日本語ラベル 2004/7/31(土)18:59 竹の (281)

┣【290】 re(4):X11での日本語ラベル 2004/8/8(日)21:52 竹の (342)

┣【300】 gnuplot-mode (re:X11での日本語ラベル) 2004/8/12(木)16:22 mario (908)

┣【304】 re(1):gnuplot-mode (re:X11での日本語ラベル) 2004/8/12(木)20:38 竹の (958)

┣【318】 re(2):gnuplot-mode (re:X11での日本語ラベル) 2004/8/17(火)16:15 mario (721)

┣【319】 re(3):gnuplot-mode (re:X11での日本語ラベル) 2004/8/17(火)17:46 竹の (1118)

┣【329】 re(4):gnuplot-mode (re:X11での日本語ラベル) 2004/8/27(金)15:24 mario (387)

┣【330】 re(5):gnuplot-mode (re:X11での日本語ラベル) 2004/8/27(金)17:49 竹の (504)