After you've installed the Apache web-server and php on Ubuntu, you find out there is no mod_rewrite installed and available.
Here is how to install mod_rewrite on Ubuntu 12.04 (actually, this is actual for at least Apache on Ubuntu 6.04).
Launch a terminal and run:
sudo a2enmod rewrite
Restart apache. Done.