ubuntu のサーバー版を通常にインストールしたときは、クライアント版や Windows のようなグラフィカルな画面がインストールされなかったはずです。
グラフィックの存在しない遙か昔のテキスト コンソールを使用する状態でインストールされるはずです。
このテキスト コンソールには 1 バイト系文字、つまり英数文字しか表示できません。
このため、漢字、かなのようなマルチ バイト系文字はすべて文字化けします。

解消するのは、グラフィカル フレームバッファを使用してマルチ バイト系文字を表示できるようなテキスト コンソールを現在のテキスト コンソールに被せるか、クライアント版や Windows のようなグラフィカルな画面 (GUI) に切り替えて使うかのどちらかの方法が必要です。

実際に試したわけではないので、適切なアドバイスになるかは分かりませんが、前者は以下の Web ページが
Ubuntuサーバーの日本語化－文字化けに対処する！ | Linux | 経済的自由を得てセミリタイヤ－悠々自適生活！

後者は以下の Web ページが参考になるかと思います。
Ubuntu 14.04 LTS : デスクトップ環境インストール ： Server World

なお、サーバー版を使うような人はインストールしたマシンのコンソールは極限られた用途にしか使わないので、そのコンソールは英語モードで動作するように設定します。
そして、日常の使用は漢字表示できるように設定した ssh でリモート接続して使用します。