If you’ve just installed WordPress and your WordPress permalinks are not working, this might help you out.

Firstly, make sure you have an .htaccess file. This should be in the root folder of your installation. If it is not there you will need to create it.

1. First, create an .htaccess file in your WordPress directory. touch /pathtowordpress/.htaccess
2. Next, give ownership of this file to the Apache2 user. sudo chown www-data "/pathtowordpress/.htaccess
3. Now type sudo a2enmod rewrite to enable mod_rewrite.
4. Now restart Apache2 using sudo service apache2 restart
5. Lastly, go into WordPress admin, then go to Settings -> Permalinks. Make your changes and hit Save.

Possible Steps Also Required:

Edit the file /etc/apache2/sites-enabled/000-default and change AllowOverride None to AllowOverride All for /var/www. Then restart Apache2 again.

Reference:
http://wordpress.org/support/topic/solved-permalinks-working-in-apache2-ubuntu-1010