There are several solutions that require the Apache module mod_rewrite to provide clean urls for better search engine optimization. One common problem if you are seeing 404 errors is the default settings in Apache does not allow you to use mod_rewrite.
By default the settings for AllowOverride is set to None. For mod_rewrite to work AllowOverride at a minimum needs to be set to FileInfo Options. Options isn’t required for mod_rewrite but is commonly required if you are using .htaccess.