If you are using Drupal, clean URLs may not work out of the box on your Ubuntu machine. You would need to enable mod_rewrite module on your apache to do that.
Therefore, first enable the module as follows:
sudo a2enmod rewrite
Change all occurrence of "AllowOverRide None" to "AllowOverRide All". Basically all "None" to "All" in the following file:
sudo vi /etc/apache2/sites-available/default
Restart Apache:
/etc/init.d/apache2 restart
You are done. Your Drupal install should have clean-urls working now.
