Did you remember to change the name of the htaccess.txt to .htaccess (or copy the contents)?
We have a flash tutorial for setting up SEF URLs available for each version of Joomla in this knowledgebase. Just use the search function.
If you are running a third party SEF solution make sure to open your .htaccess file and make the changes suggested in the file.