Mod_rewrite is a module for the Apache web server tha, among other things, allows for things like rewriting long, cumbersome, Google unfriendly URLS like http://yoursite.com/?m=3421 into something like http://yoursite.com/my-first-post.
Basically, to use the code generated in the permalinks option page, copy it, and open up your text editor. Paste it in a new document, then save the document as '.htaccess'. This needs to go in your root WP directory (the directory that contains all your WP files and folders.) Simple as that, assuming your server has mod_rewrite installed.
If it works, then it does. If it doesn't, there could be other problems, but the first thing to check is your hosting company, to see if they do in fact have it installed.