Download and install the quake2-data package from any of these mirrors: quake2-data deb.
You will then need to insert the CD, and run the following command at the console:
sudo dpkg-reconfigure quake2-data
You will need to insert the CD mount point, on Ubuntu this is probably /media/Quake2
If you opt to install the point release update then you will also have to specify where to download the file to. /home will work fine.
Once this is done you will need to download a Linux compatible Quake2 engine - I used yamagi (download the yamagi quake2 deb).
Then just run yamagiq2 from the terminal, and enjoy.