xemacsは、Ubuntuにパッケージが用意されています。
特別にビルドする必要がなければ、Synapticからインストールできます。

ビルドする必要があるならば、
＞checking whether the C compiler(gcc)works...no
コンパイラが入ってません。
開発環境と必要なライブラリのdevパッケージを入れてください。

Synapticパッケージマネージャを見てみましたが、
xemacs２１は見あたりません。
検索でxemacs21とやってみると、画面左側に
全て
xemacs21
と表示されますが、操作できません。

>「設定」→「リポジトリ」で，ソフトウェアソースの画面を開き，
>□ コミュニティによるメンテナンスされるオープンソースソフトウェア(universe)
>にチェックを入れて，再読み込みを実行。

>その後，もう一度検索してみて下さい。

やってみましたが、画面左側にxemcs21と表示されるだけです。
操作できません。

インターネットはつながっています。

>操作できないというのは，どういう意味でしょうか？
>右側のウィンドウにもxemacs21という項目が表示されていませんか？
操作というのは、クリックしても反応がないということですが。
右側のウィンドウにはなにも表示されません。

>追記：コメントで「xemcs21」になっていますが，スペルミスしていませんか？
xemacs21ですね。スペルミスです。

tamaki@tamaki-desktop:~$ sudo apt-get update
[sudo] password for tamaki:
無視 cdrom://Ubuntu 7.10 _Gutsy Gibbon_ Japanese Remix - Release i386 (20071018) gutsy/main Translation-ja
無視 cdrom://Ubuntu 7.10 _Gutsy Gibbon_ Japanese Remix - Release i386 (20071018) gutsy/restricted Translation-ja
取得:1 http://archive.ubuntu.com gutsy Release.gpg [191B]           
取得:2 http://archive.ubuntu.com gutsy/universe Translation-ja [332kB]
ヒット http://archive.ubuntu.com gutsy Release                                 
ヒット http://archive.ubuntu.com gutsy/universe Packages                       
332kB を 53s で取得しました (6250B/s)                                         
パッケージリストを読み込んでいます... 完了

どうやらUniverseしかリポジトリが有効になっていないようです。

vine_user による投稿:

universeリポジトリに入っていますよ。

「設定」→「リポジトリ」で，ソフトウェアソースの画面を開き，
□ コミュニティによるメンテナンスされるオープンソースソフトウェア(universe)
にチェックを入れて，再読み込みを実行。

その後，もう一度検索してみて下さい。

上記の手順でリポジトリ設定を行い、main, restrictedの2つを有効にして再度試してみてください。

それでもダメな場合、
$ cat /etc/apt/sources.list
の結果を見せてください。

.emacs に UTF-8 で日本語を扱う設定がされてないのでは？
xemacs は知りませんが、21 までの emacs は mule-ucs をインストールして適切に設定をする必要があります。お使いの .emacs ファイルを見せていただくと、アドバイスがもらえるかもしれません。

emacs で日本語を扱う基本的な設定は wiki にページがあるので参考にしてください
https://wiki.ubuntulinux.jp/UbuntuTips/Application/EmacsJapaneseSetup

$ less .emacs
.emacs : No such file or directory
$ less ~/.emacs
bash:/home/tamaki/.emacs: No such file or directory
$ emacs
プログラム'emacs'は以下のパッケージで見つかりました:
* emacs21-nox
* emacs22-gtk
* emacs22
* e3
* emacs-snapshot
* emacs-21
* emacs-22-nox
* jove
* emacs-snapshot-gtk
次の操作を試してください: sudo apt-get <選択したパッケージ>
bash: emacs: command not found
$ sudo apt-get install emacs21
パッケージリストを読み込んでいます...完了
依存関係ツリーを作成しています
Reading state information...完了
以下の特別パッケージがインストールされます:
emacs21-bin-common emacs21-common liblockfile1 libungif4g xaw3dg
提案パッケージ
emacs21-common-non-dfsg emacs21-el
以下のパッケージが新たにインストールされます:
emacs21 emacs21-bin-common emacs21-common liblockfile1
libungif4g xaw3dg
アップグレード: 0個、新規インストール: 6個、削除: 0個、保留: 0個。
11.8MBのアーカイブを取得する必要があります。
展開後に追加で42.0MBのディスク容量が消費されます。
続行しますか[Y/n]? Y
取得: 1 http://archive.ubuntu.com gutsy/universe emacs21-common 21.4
a+1-5ubuntu4[4358kB]
取得: 2 http://archive.ubuntu.com gutsy/main liblockfile1 1.06.2[14.8kB]
取得: 3 http://archive.ubuntu.com gutsy/universe emacs21-bin-common21
.4a+1-5ubuntu4[147kB]
取得: 4 http://archive.ubuntu.com gutsy/main libungif4g 4.1.4-5[58.6kB]
取得: 5 http://archive.ubuntu.com gutsy/main xaw3dg 1.5+E [156kB]
取得: 6 http://archive.ubuntu.com gutsy/universe emacs21 21.4a+1-5ubun
tu4[2024kB]
11.8MBを25m59sで取得しました（7538kB)
未選択パッケージemacs21-commonを選択しています。
(データベースを読み込んでいます...現在95590個のファイルとディレクトリが
インストールされています。)
(.../emacs21-common_21.4a+1-5ubuntu4_all.debから)emacs21-common
を展開しています...
.
.
emacs21-common(21.4a+1-5ubuntu4)を設定しています...

liblockfile1(1.06.2)を設定しています...
emacs21-bin-common(21.4a+1-5ubuntu4)を設定しています...

libungif4g(4.1.4-5)を設定しています...
xaw3dg(1.5+E-15)を設定しています...

emacs21(21.4a+1-5ubuntu4)を設定しています...
emacs-install emacs21
install/dictionaries-common: Byte-compiling for emacsen flavor emacs21
Wrote /usr/share/emacs21/site-lisp/dictionaries-common/debian-ispell
.elc
Wrote /usr/share/emacs21/site-lisp/dictionaries-common/ispell.elc
Wrote /usr/share/emacs21/site-lisp/dictionaries-common/flyspell.elc
Done
emacsen-common: Handling install of emacsen flavor emacs21
emacsen-common: byte-compiling for emacs21
Loading 00debian-vars(source)...
No /etc/mailname.Reverting to default...
Loading 50dictionaries-commom(source)...
Loading /var/cache/dictionaries-commom/emacsen-ispell-default.el
(source)...
Loading /var/cache/dictionaries-common/emacsen-ispell-dicts.el(source)
...
Wrote /etc/emacs21/site-start.d/00debian-vars.elc
Wrote /usr/share/emacs21/site-lisp/debian-startup.elc
Done

processing triggers for libc6...
ldconfig deferred processing now taking place
$ sudo apt-get install mule-ucs
パッケージリストを読み込んでいます...完了
依存関係ツリーを作成しています
Reading state information...完了
提案パッケージ
xfonts-jisx0213
以下のパッケージが新たにインストールされます
mule-ucs
アップグレード: 0個、新規インストール: 1個、削除: 0個、保留: 0個。
728kBのアーカイブを取得する必要があります
展開後に追加で4927kBのディスク容量が消費されます。
取得: 1 http://archive.ubuntu.com gutsy/universe mule-ucs 0.85~0.2006
1127-2[728kB]
728kBを1m38sで取得しました(7369B/s)
未選択パッケージmule-ucsを選択しています。
(データベースを読み込んでいます...現在96770個のファイルとディレクトリが
インストールされています。)
(.../mule-ucs_0.85~0.20061127-2_all_debから)mule-ucsを展開しています...
mule-ucs (0.85~0.20061127-2)を設定しています...
install/mule-ucs: Byte compiling for emacs21...This will take a while...done.
install /mule-ucs: Byte-compiling for xemacs21...This will take a while
...done.
$ .emacs
bash: .emacs: command not found
$ emacs
-u:--*scratch*  (Lisp Interaction)  <-まだ文字化け
$ xemcs    <-まだ文字化け
$ vi .emacs      （.emacsファイルがないので自分で作成)
$ xemacs
(1) (initialization/error)An error has occurred while loading/home/tamaki
/.emacs:
Can't prefer the coding system 'utf-8'

To ensure normal operation, you should investigate the cause of the error
in your initialization file and remove it. Use the '-debug-init' option to XEma
cs to view a complete error backtrace.
u--**-XEmacs: *Warning*   (Fundamental)
Migrate init file to ~/.xemacs/? (yes or no) no
.......
/home/tamaki/.emacs
be migrated to the ~/.xemacs/directory. XEmacs can perform the migration
automatically.

After the migration, init.el/init.elc holds user-written initialization code. More
over the customise settings will be in custom.el.

You can undo the migration at any time with M-x maybe-unmigrate-user
-init-file.
u-----XEmacs: *Help   (Fundamental)
Wrote /home/tamaki/.emacs

$ emacs
-u: **  *scratch* (Lisp Interaction)
Symbol's function definition is void: set-default-coding-system
To ensure normal operation, you should investigate the case of the error
in your initialization file and remove it. Start Emacs with the '--debug-init'
option to view a complete error backtrace
$ vi .emacs
(記述した文を削除)
(custom-set-variables
'(load-home-init-file t t))
(custom-set-faces)
$ emacs
*Message*
Error in init file: Symbol's value as variable is void:
$ vi .emacs
(この行、削除)
(custom-set-variables
'(load-home-init-file t t))
(custom-set-faces)
$ emacs
Error in init file: Symbol's value as variable is void:
$ ls -a
.emacs
.emacs~
$ rm -i .emacs
rm: remove 通常ファイル '.emacs'? y
$ rm -i .emacs~
rm: remove 通常ファイル '.emacs~'? y
$ emacs     (エラーなし)
$ sudo apt-get install emacs-env-ja
パッケージリストを読み込んでいます...完了
依存関係ツリーを作成しています
Reading state information...完了
E:  パッケージ emacs-env-jaが見つかりません
$ sudo apt-get install emacs22-gtk
パッケージリストを読み込んでいます...完了
依存関係ツリーを作成しています
Reading state information...完了
以下の特別パッケージがインストールされます:
emacs22-bin-common emacs22-common
提案パッケージ
emacs22-el
以下のパッケージが新たにインストールされます:
emacs22-bin-common emacs22-common emacs22-gtk
アップグレード: 0個、新規インストール: 3個、削除: ０個、保留: 0個。
20.7MBのアーカイブを取得する必要があります。
展開後に追加で64.7MBのディスク容量が消費されます。
続行しますか[Y/n]? Y
取得: 1 http://archive.ubuntu.com gutsy/main emacs22-common22.1-0
ubuntu5[18.6MB]
取得: 2 http://archive.ubuntu.com gutsy/main emacs22-bin-common 22.1
-0ubunt5[161kB]
取得: 3 http://archive.ubuntu.com gutsy/universe emacs22-gtk 22.1-0
ubuntu5[1950kB]
20.7MBを45m38sで取得しました(7555B/s)
未選択パッケージemacs-commonを選択しています。
(データベースを読み込んでいます...現在96865個のファイルとディレクトリが
インストールされています。)
(.../emacs22-common_22.1-0ubuntu5_all.debから)
emacs22-commonを展開しています...
.
.
emacs22-common (22.1-0ubuntu5)を設定しています...

emacs22-bin-common(22.1-0ubuntu5)を設定しています...
emacs22-gtk(22.1-0ubuntu5)を設定しています...
Byte-compiling add-on packages, please wait...done.

$ emacs22-gtk
　日本語。できました。
入力しようとすると、ボックスができて、そこに入力するようになっているのです
が、こんなものでしょうか。

emacs-env-ja が見つからないということは、日本語ローカライズ版のリポジトリを有効にしていないのでしょうか。
ボックスが出てきて日本語入力をしているということは、Gnome 上の SCIM から入力をしている状態です。Emacs 上でインライン入力をするためには、anthy-el をインストールする必要があります。これは当然 emacs-env-ja メタパッケージを使用すれば同時にインストールされます。
今回の場合は既に Emacs22 が動作しているようなので、anthy-el をインストールしてください。そして .emacs に

(load-library "anthy")
(setq default-input-method "japanese-anthy")

と書くだけでよいはずです。

anthy-el を起動して透過モードから変換モードに切り替えるのは C-\ です。C-Space や 半角/全角 キーでは当然 scim が立ち上がります。

Anthy-el の使い方
http://anthy.sourceforge.jp/cgi-bin/hiki/hiki.cgi?Emacs%A4%AB%A4%E9