Open up conf/settings.php and add this line:

$Configuration['URL_BUILDING_METHOD'] = 'mod_rewrite';

Believe me, that's all you need to do. Ain't that easy?
Note: I am assuming that you are using Apache HTTPD Web Server with mod_rewrite enabled.
Note 2: I have tested it on windows but I have all reasons to believe that it will work fine on Unix / Linux too. Normally Windows is the harder one to solve as far as Apache is concerned :)