In order to enable Clean URLs module on Drupal, an Apache server module named mod_rewrite has to be enabled. The following is the procedure to do it on Ubuntu which has LAMP installed using tasksel.
The mod_rewrite on Ubuntu LAMP is not enabled by default. It can be enabled by running the following command on the terminal.
sudo a2enmod rewrite
This will enable the mod_rewrite module on Apache. Now restart Apache server by running.
sudo /etc/init.d/apache2 restart