How are you hosting your site?
If you’re on shared hosting, reset your permalinks from settings->permalinks.
If you are on a VPS that you set up yourself, add these lines to your apache/httpd configuration for this virtual host:
<Directory /path/to/wordpress>
AllowOverride All
</Directory>
then restart apache/httpd
* note /path/to/wordpress
is probably something like /var/www/html