Ubuntu or any Debian based Linux users can install the required package with apt-get:
sudo apt-get install php5-mcrypt
Remember to restart the web server afterwards:
sudo service apache2 restart
If it still doesn’t work, try to link the configuration file to the appropriate configuration folder for the web server. Thanks to dave1010 for this hint in the comments.
sudo ln -s /etc/php5/conf.d/mcrypt.ini /etc/php5/apache2/conf.d/ # for Apache
sudo ln -s /etc/php5/conf.d/mcrypt.ini /etc/php5/cli/conf.d/ # for CLI
And again, restart the web server:
sudo service apache2 restart
Perhaps, if not working yet, you need also the line showed by @RahulPrasad, with php5enmod mcrypt.