Getting sh404SEF was easy. You could download it from http://joomlacode.org/gf/project/sh404sef/frs/, but now it is on http://dev.anything-digital.com/sh404SEF/ and you need a valid download subscription available for 35 USD a year to get the latest version for Joomla! 1.5. You still can use it for unlimited number of sites.
Don't be scared due to the fact that it is still in beta, I am using it on several web sites and have not had any problems.
Installation of the components is similar to any other component. Simply install it using the normal installer, but this time, read the screen after installation or even print it.
This screen has a lot of information on how to make sure the SEF URLs are as clean as you want them to be. If you closed the screen and missed the information, you can read it again in the documentation of the component, which can be reached from the component's control panel. Most important information is...