Debian squeezeのpsqlはreadlineではなくlibeditを使用しています。どうやらこれがバグ持ちのようで日本語入力できないようです。
試しに、psql -nでreadlineを使用しないオプションをつけると日本語入力が可能になります。しかしこの場合にはヒストリーとかのreadlineの機能が使えないので解決方法としてはちょっといまいち。結論はlibreadlineを使用したパッケージを作り直すしかありません。
時間はかかりますがが、今回のパッケージの作成はそれほど難易度は高くありません。

$ apt-get source postgresql
$ cd postgresql-8.4-8.4.7
$ vi debian/control

8行目のlibedit-devをlibreadline-devに書き換える

$ fakeroot dpkg-buildpackage -us -uc

必要なライブラリが提示されるので、それらをガンガン、インスールする。

仕切り直してもう一度。

$ fakeroot dpkg-buildpackage -us -uc

一つ上のディレクトリにパッケージが山ほどできあがります。