Are you using XAMPP or MAMP? There are a couple of common hiccups with those environments, taken from the WordPress Codex: Fixing Permalink Problems
Users of XAMPP (Windows): Some versions of XAMPP do not enable
mod_rewrite by default (though it is compiled in Apache). To enable it
— and thus enable WordPress to write the .htaccess file needed to
create pretty permalinks — you must open apache/conf/httpd.conf and
uncomment the line LoadModule rewrite_module modules/mod_rewrite.so
(i.e., delete the hash/pound sign at the front of the line).
Users of WAMP (Windows): Some versions of WAMP (all versions?) do not
enable mod_rewrite or permit following SymLinks by default. To enable
the required functionality navigate to the apache/conf/httpd.conf
file, open with a text editor and uncomment the line LoadModule
rewrite_module modules/mod_rewrite.so (i.e., delete the hash/pound
sign at the front of the line). Then further down in the same file
there is a section that starts with the line "Options FollowSymlinks".
Change the second line in that section from "AllowOverride none" to
AllowOverride all. Save edited httpd.conf and restart all WAMP
modules. Your permalinks should now work.
You might also see Permalinks without mod_rewrite if your sandbox doesn't have mod_rewrite
available.
Apache
If you are using Apache there are usually two other culprits to broken permalinks: .htaccess
isn't being generated (because of permissions settings) or Apache's AllowOverride
directive isn't enabled.
First, if you SSH into your server, do you see a generated .htaccess file in the root? If not, WordPress might not have permissions to write that file. It's also possible the file does exist, but that WordPress cannot edit it. In either case, you can chmod
that file (and create it if it doesn't exist) to 666.
Next, ensure your Apache config has the following settings:
<Directory />
Options FollowSymLinks
AllowOverride All
</Directory>
Finally, read through the Fixing Permalink Problems section of the WordPress Codex. There are several other tips and suggestions on why permalinks might not work.