For apache webserver you should use mod_Rewrite.
Modify .htaccess file according to
http://www.askapache.com/htaccess/mod_rewrite-tips-and-tricks.html
also you need to implement smarty outputfilter to replace all the hyperlinks on the pages.
If I'm not mistaken CD SEO Pro mod can do all this job for you but it will also make all the upgrades of X-cart very painful.
So if you don't plan to upgrade your 4.1.9 CD SEO Pro is a right solution for you