From B2evolution

The default permalinks in b2evolution look something like:
http://www.yoursite.com/blogs/index.php?title=post_title&c=1&tb=1&pb=1&more=1

You can change this behavior to something cleaner by going to the backoffice under the Blog Settings > URLs tab. There you can choose different link formats. For example:
http://www.yoursite.com/blogs/index.php/2003/05/20/post_title

On the Settings|General tab you can also set different "Permalink type" options which determine whether your links are referenced by their database ID or by the title.

Also, by installing b2evolution at the root of your website -- without using a blogs folder -- your permalinks would show like this: http://www.yoursite.com/index.php/2003/05/20/post_title

[edit] Going further with mod_rewrite

Here's how to get rid of index.php and make your urls look more like this:
http://www.yoursite.com/2003/05/20/post_title

Edit the .htaccess file at the root of your site and add the following lines:

 RewriteEngine On
 
 # Redirect anything that's not an existing directory or file to index.php
 RewriteCond %{REQUEST_FILENAME} !-d
 RewriteCond %{REQUEST_FILENAME} !-f
 RewriteRule ^  index.php

Once this is done, go to your blog settings > URLs and select "Default blog on index.php" for example.

[edit] _ vs -

With b2evolution 2.0, underscores are changed into dashes/hyphens. The permalink would look like this:
http://www.yoursite.com/2003/05/20/post-title