1. This is mostly true. Google will index some pages that include query strings (that's the stuff after the ?), but your best bet is to use "search-engine-friendly" or "non-cruft" URLs via mod_rewrite.
2. mod_rewrite is currently the best tool for this if you're running Apache. I checked out bimmercenter.com, and from what I can see, it doesn't seem to be loaded, but you should check yourself to be sure.
I'm going to assume that you're self-hosting and not dealing with a managed host that could do this for you.
You'll need to access your httpd.conf file and look for the mod_rewrite library. If you find it, it's possible that it's commented and that's why it's not running. Just erase the # from the beginning of the line.
Here's a thread on an off-site forum that might be of use to you for getting mod_rewrite installed assuming it's not simply disabled on your system.
After mod_rewrite is running (Netcraft for your site might help you out viewing server headers, but there's probably a better way), you can get the configuration for mod_rewrite directly from the WordPress admin panel on the Options/Permalinks page.
This is just a quick overview of the basic steps to get mod_rewrite going. You might like to read up on the module and what it does over at the Apache site itself, because the module is quite powerful and configurable.
An alternate method of getting cruft-free URLs is only available in the bleeding-edge cvs version of WordPress. WordPress 1.3 looks like it supports PathInfo, which is a clever way to avoid using mod_rewrite entirely. You'll need to add an ErrorDocument line to your httpd that redirects 404 errors to your WordPress index page. WordPress will figure out what to do from there using your Permalink settings.