Did you turn it on in your global configuration? (from joomlas admin backend)
Rename/ and configure your .htaccess file? (these settings depend upon what your server/hosting setup is)
Top two reasons for it not working above.
Are you on an apache server with mod_rewrite enabled?
Sorry to answer your question with a few questions... I'll be back in about 7 or 8 hours and check up on this post, sadly I am on my way out the door......
Cheers!
Do not go where the path may lead, go instead where there is no path and leave a trail.