For php5 on Ubuntu 14.04
sudo apt-get install php5-intl
For php7 on Ubuntu 16.04
sudo apt-get install php7.0-intl
For php7.2 on Ubuntu 18.04
sudo apt-get install php7.2-intl
Anyway restart your apache after
sudo service apache2 restart
IMPORTANT NOTE: Keep in mind that your php in your terminal/command
line has NOTHING todo with the php used by the apache webserver!
If the extension is already installed you should try to enable it. Either in the php.ini file or from command line.
Syntax:
php:
phpenmod [mod name]
apache:
a2enmod [mod name]