Here a quick guide how to get them to work on Ubuntu. This guide was tested on Ubuntu 10.10 but should work fine on other versions.
There is no precompiled DEB package available, however once the dependencies have been resolved compiling the packages is easy.
Installing the dependencies
The key package I needed for sucessful compiling is called med-bio. Install it via the following command in a terminal window or install the package via the Ubuntu Software Center.
sudo apt-get install med-bio
Once this is installed you can start compiling.
Getting the sources and compiling them
Now, for each of the two extracted source code packages do the following commands one after the other and start with the Vienna RNA Package.
./configure make sudo make install
To test if RNAz installed well type the following command and you should get the installed version number as an output.