fedoraでJavaからアクセスできるフォント一覧取ってみたところ、日本語表示できるのは

java.awt.Font[family=UnDotum,name=Un Dotum,style=plain,size=1]
java.awt.Font[family=UnDotum,name=Un Dotum Bold,style=plain,size=1]
java.awt.Font[family=VL ゴシック,name=VL Gothic Regular,style=plain,size=1]
java.awt.Font[family=WenQuanYi Zen Hei,name=WenQuanYi Zen Hei,style=plain,size=1]
java.awt.Font[family=WenQuanYi Zen Hei Mono,name=WenQuanYi Zen Hei Mono,style=plain,size=1]
java.awt.Font[family=WenQuanYi Zen Hei Sharp,name=WenQuanYi Zen Hei Sharp,style=plain,size=1]

位か。最初の2つはちょっと化ける文字があるので駄目。フォントが日本語を表示できるかどうかをプログラム中から見分ける方法は無いかしら。
素直にリスト作って持っておくか。しかしそもそも上記のは標準的なものなのかな。
VLゴシックが割と普及してるらしいのでLinuxから起動されたらこれにしとくか。

Vine Linux 4+, VineSeed, Debian GNU/Linux, Fedora 9+, Ubuntu 8.04-9.10で日本語の標準フォントとして採用されています。

Vine Linux 5/4
Debian GNU/Linux
Ubuntu
Fedora 9 / Fedora 8 / Fedora Extras 6 / Fedora Extras 5
Gentoo Linux
FreeBSD
NetBSD
PC-BSD

http://vlgothic.dicey.org/distribution.html

Debian,Fedora,Ubuntu、うむ、まぁ充分だろ。