The unofficial Ubuntu repository Akirad now hosts packages for easy install of Frei0r plugins. Akirad also hosts things like Cinelerra and Open Movie Editor which is not in the official Ubuntu repositories.
Check it out here:

Here’s how to install Frei0r on your Ubuntu Hardy box:

sudo wget -O /etc/apt/sources.list.d/akirad.list
wget -q -O- | sudo apt-key add – && sudo apt-get update
sudo apt-get install frei0r-plugins