If you are hosting yourself, you’ll need to install the mod_rewrite module, then set up your .htaccess as WordPress tells you to (when you set up your Permalink structure).
If you are hosted somewhere else, you’ll have to get in contact with your Tech Support people, and have them install the mod_rewrite module.
