Instale o pacote xutils-dev .
Para procurar informações semelhantes, use o comando apt-file find , por exemplo
apt-file find xmkmf .
Eu gostaria de compilar o FreeNX assim
aptitude install build-essential
apt-get install subversion patch
apt-get install expat fontconfig xterm zlib1g libgl1-mesa-dri libgl1-mesa-glx libglu1-mesa libpng12-0 libdrm-intel1 libdrm-nouveau1a libdrm-radeon1 libdrm2 libfreetype6
apt-get install zlib1g-dev libjpeg62 libjpeg62-dev libpng12-0-dev
svn checkout svn://svn.berlios.de/freenx/trunk
cd /root/trunk/freenx-server
patch -p0 < gentoo-nomachine.diff
make
make install
mas make falha porque não consegue encontrar xmkmf que parece ser um programa para criar o Makefile.
Alguém sabe como obter / instalar xmkmf no Ubuntu?