Permalinks require mod_rewrite and .htaccess
Steps:
1. To enable mod_rewrite in Ubuntu, you just need to write this command in terminal
sudo a2enmod rewrite
Restart apache2 after this by typing “service apache2 restart”
2. To get Permalinks working you will need to place an .htaccess file in your wordpress’s web directory(/var/www or /var/www/<blogname> in case of multiple blogs on same host) and add the following:
# BEGIN WordPress
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ – [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
# END WordPress
3. Change the permissions on the .htaccess file to “chmod 666” so wordpress can update it when you switch permalink patterns from the settings page
Note: This is a hidden file so it will only show up when you type “ls -altr“
4. Open up the following file, and replace every occurrence of “AllowOverride None” with “AllowOverride all” (note : “all” should be in lower-case for this to work)
1) sudo nano /etc/apache2/sites-available/default
2) sudo service apache2 restart
5. Change the permalink in WordPress admin console(http://your-wordpress-domain/wp-admin.php) to what you want by going to Settings -> Permalinks -> and clicking to “Save Changes”.
This will update the .htaccess file. Double-check this by checking the timestamp of the .htaccess file after clicking “Save changes” on WordPress admin console
Resources:
https://www.digitalocean.com/community/questions/wordpress-permalinks-broken
https://www.digitalocean.com/community/questions/ubuntu-12-04-lamp-wordpress-htaccess-errors
http://mahmudahsan.wordpress.com/2008/07/06/ubuntu-enable-mod_rewrite-in-apache-server/