Implementing 100% SEF URLs in Joomla!! can be a little tricky so we've written a step-by-step guide that includes how to correctly configure your LAMP server.
There are some differences in implementing SEF URLs in Joomla! 1.0.* and 1.5, principally the requirement for third-party plugins.
Practical advice is available here.