In case you .htaccess exists and is placed in the right directory you should check if it has the right permissions and if the right user owns it. The right user should be your linux user handling WordPress. On Debian (it will be similar on other systems, I suppose) you can find the owner and the permission of a file or directory with the command  ls -l /path/to/directory. The output will tell you the permission on the file (”-rw-r–r–” in my case) and who owns the file (”www-data” in my example). The second ”www-data” indicates the group, which is identical than the owner in my case.

ls -l /var/www/html/.htaccess
-rw-r--r-- 1 www-data www-data 282 Jul 28 20:38 /var/www/html/.htaccess

Theoretically, every permission between 644 (-rw-r–r–) and 604 (-rw—-r–) should work fine. However, WordPress recommends to use a 644 permission for .htaccess files. In case your file has the right permissions and is owned by the right user you should move on the point 3 of the checklist. However, in case you do not have the proper specifications you can adjust the the following way.

chown username:group path/file
chmod permission path/file

In my case if would be

chown www-data:www-data /var/www/html/.htaccess
chmod 644 /var/www/html/.htaccess

Note, you must have the necessary permissions to execute this commands. You might have to log in with su or sudo.
Finally, you should restart Apache so that you websever applies you changes.

service apache2 restart

Hopefully you were able to solve you permalink problems by now. Otherwise move to point 3 of the checklist.

Checklist

1. .htaccess must be present in the same folder as index.php
2. .htaccess be writeable
3. apache2.conf must allow overwrite
4. database problems