This tip covers configuration in Options/Permalinks [Edit Permalink Structure] for WordPress users. My version is WordPress 1.5.

By default WordPress uses a query string to identify a post. This is neither search engine friendly nor human friendly. A better way is to use a custom URI to better identify your posts. Many bloggers include a date as part of the permalink. I advise against it. The date of the post is not so important as to be part of the URI!

My suggestion is to use a simple structure containing the post-slug as your Permalink URI. I use:
Structure: /index.php/archive/%postname%/

Note that there is an index.php embedded. This is fine with search engines and humans too. And it will work great. It doesn't require mod_rewrite functionality or change to htaccess. Something as simple as this will work in all configurations.

For category base I use simply: /index.php/category

This is just a simple example. You can make your URI as complicated as you want. Just remember to test it.
Personally I like it short and simple.

Update 1: Please refer to the comments below for points and counterpoints on this topic.

Update 2: The objections raised by some people is that having an identical named title for posts will cause problems with WordPress. This is not a valid observation anymore. In other words you can have 10 posts named "Happy New Year" and WordPress will assign unique post-slug to each. Simply said this approach is without any drawbacks AFAIK.

Update 3: Cem commented:

For future reference, I was able to get permalink URL rewriting working in WordPress by creating a php.ini at my domain root with the following configuration:

cgi.fix_pathinfo = 1
cgi.force_redirect = 0

Several people have found it useful on various environments including but not limited to IIS on windows as can be seen from the comments. Thanks Cem for sharing!

BTW: Personally I use /archive/%postname%/ for my Stem Cell Research Blog without requiring any changes.

The greatest benefit is that you don't have to embed index.php as part of URL, possibly slightly increasing your SERP.