First check that you have a .htaccess file in your WordPress root folder (the one that contains your wp-config.php file). If it's missing, copy the following text (source) into a new plain-text file called .htaccess in the WordPress root folder. Also, make sure this file is readable by Apache (permissions of 0644 should suffice).
# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
# END WordPress
If that doesn't help, then your Apache server doesn't support the use of RewriteRule directives. This is most likely because mod_rewrite isn't enabled for your particular domain. To fix this, you need to edit the Apache configuration file and add this line to the configuration statements that apply to your domain:
Options +FollowSymLinks
The location of the Apache configuration files can vary depending on your hosting setup, but try looking for a file called httpd.conf in /etc/httpd/conf/.
Check your server's error log too. There might be some useful information in there.