Yes, mod_rewrite is what you want if you are using Apache.
If anybody has any proof, I'd like to see it, but the official word from Google and others is that data-driven content (.ASP, .PHP, .JSP, etc.) is not a problem for their spiders. The only problem for spiders associated with data-driven pages is speed. A spider obviously "browses" your site a lot faster than a human. It may request a dozen pages in a single second. Spiders are not as patient as most humans, either. If your page takes 5 seconds to return--whether static or data-driven, the spider may consider the link bad and move on.
My point is that jumping through hoops to make your data-driven pages LOOK like static pages doesn't help your pages load any faster--which is the real issue with search engines--at least Google anyway.
Google has a Facts & Fiction page here that explains they can index dynamic pages.
http://www.google.com/webmasters/facts.html
At least for google, querystrings are not an issue either, although they do recommend you keep your querystrings short with only a few parameters.
Another "secret" is that if the only way to get to your pages is via a search on your site, then a spider will never find them. You do need every page that you want indexed somehow linked from another page. For example, if your site sells fruit, and the only way for me to reach your fruit_detail.php?fruit=apple page is by searching your inventory for "apple", then a bot will not find this page. However, if I can click on "Inventory" in your menu, then click "Apples" on your page listing all the fruit you sell, a bot can follow these links, too. (This assumes your menu is not generated by javascript, does not require javascript to navigate, and is not a Flash movie menu.)
This is a huge topic, and should be discussed in
http://www.daniweb.com/techtalkforums/forum45.html, but one last tip I can offer is to remember you need standard links to your content. If a link has a target like <a href="javascript
:LoadPage('fruit.htm')">Fruit</a>, a spider will not be able to follow this link since they cannot run client-side script.