This is to install the Parallels Tools into a stock install of Ubuntu Server 10.04.  I don't use a GUI on servers so, that would probably involve several additional steps I won't go into here.

1. Download the Ubuntu Server 10.04 ISO (64-bit)
2. Open Parallels, "Add New"
3. Select the ISO file.
4. Skip detection.
5. Follow all the defaults, including through the Ubuntu install.
6. Once Ubuntu is installed, execute the following:

   sudo apt-get install linux-headers-$(uname -r) build-essential
   cd /media/apt
   sudo sh ./install

Say yes if it asks you to install some additional components.

Reboot.

You'll know if the Parallels Tools are installed correctly upon reboot, because in the Parallels Menu under "Virtual Machine" it will have a "Re-install Parallel Tools" option instead.