Mod_Rewrite is a set of functions built into .htaccess, an Apache module which allows for all sorts of nifty tricks with URL's, Error Pages, etc.
Mod_Rewrite specifically is used mostly for changing dynamic links, such as:
http://www.example.com/shop.php?cat=4&id=123
into search engine friendly static URL's, such as:
http://www.example.com/shop/4/123.html
While the dynamic link won't get indexed easily, and likely not at all without external sites linking directly to that URL, the static link will get indexed with simple internal linking.
Mod_Rewrite is a very powerful tool for creating static links for content management systems, forums, and the like. From personal experience, after converting dynamic links on a games website I run to static links using .htaccess, my search engine results have multiplied many times over.