This is one of those things I often forget to do when setting up WordPress on a new server, which means pretty permalinks don’t work: If you have a problem with permalinks not working on WordPress, it may be because Apache does not have mod_rewrite enabled.
An easy way to check is to make a simple php script, saved in the root directory of your webserver as info.php (or whatever takes your fancy):
<?php phpinfo(); ?>
This will give you an output of all the various modules and settings you have enabled for Apache. If you don’t see mod_rewrite under the Loaded Modules section, you need to enable it.
In Ubuntu this is pretty simple:
$ sudo a2enmod rewrite
Don’t forget to restart Apache
$ sudo service restart apache