Ok, to start off, this is a big deep ugly hack that involves changing a lot of stuff, creating a file or two, and modifying the db.

Not for the faint of heart, but worth it, for the cleanness of category links.
So, instead of http://example.com/blog?cat=12, you'll have http://isaacschlueter.com/category/design

1. [url=http://forums.b2evolution.net/viewtopic.php?t=1564]Use super clean .php-less links.[/url] Add "category" to the list of blog stubs in your .htaccess file.
Important: DONT HAVE ANY BLOGS WITH A STUB OF "category" OR THIS WILL BREAK!

2. Make sure that your categories all have unique names. It won't work if you have two blogs with categories of the same name.

3. Create a new column in your evo_categories table. Call it "cat_url_title", and make it a Varchar(255) or so. (TinyText would work, too.)

4. Create a file called "category.php", and put this in it:

<?php
$ReqURI = $_SERVER['REQUEST_URI'];
$ReqArr = explode('/',$ReqURI);
$cat_url_name = $ReqArr[2];

require_once dirname(__FILE__).'/b2evocore/_main.php';

if($cat_url_name != '')
{
	$query = "UPDATE `evo_categories` set `cat_url_name` = lcase(replace(replace(replace(replace(replace(replace(replace(replace(replace(replace(`cat_name`,' ','_'),'-','_'),'/','_'),'\\\','_'),'__','_'),'__','_'),'__','_'),'__','_'),'__','_'),'__','_'))";
	$DB->query( $query );
	$query = "SELECT `cat_ID`, `cat_blog_ID` FROM `evo_categories` WHERE `cat_url_name` = '$cat_url_name'";
	$res = $DB->get_row( $query, ARRAY_A );
	
	if(is_numeric($res['cat_ID']))
	{
		$cat = $res['cat_ID'];
		$_GET['cat'] = $cat;
	}
	if(is_numeric($res['cat_blog_ID']))
	{
		$blog = $res['cat_blog_ID'];
	}
}


//spoof the requri so that b2evo don't get confused.
$ReqURI = '/index.php?cat='.$cat;
$ReqPath = '/index.php';

if( empty($blog) )$blog = $Settings->get('default_blog_ID');
if( empty($blog) )$blog=1;

$linkblog = 4;
$blogroll_blog = 4;
$linkblog_cat = '';

$cat_array[] = $cat;

require_once dirname(__FILE__)."/$core_subdir/_blog_main.php";
?>

Save it, and upload to your website.

Now, urls like http://yoursite.com/category/my_category should get you the category listing. If it doesn't work, then stop here, and start debugging. The category name in the url should be lower-case, with _ instead of space, -, \, or /. (Other funky chars could probably mess it up...)

5. If you already have a /conf/hacks.php, add this too it. If not, create a file called "hacks.php" and put it in your conf folder. Put this in it:

<?php
function category_stub_link($cat_name)
{
	$cat_name = strtolower($cat_name);
	$cat_name = str_replace(' ','_',$cat_name);
	$cat_name = str_replace('-','_',$cat_name);
	$cat_name = str_replace('/','_',$cat_name);
	$cat_name = str_replace('\\','_',$cat_name);
	$cat_name = str_replace('__','_',$cat_name);
	$cat_name = str_replace('__','_',$cat_name);
	$cat_name = str_replace('__','_',$cat_name);
	$cat_name = str_replace('__','_',$cat_name);
	$cat_name = str_replace('__','_',$cat_name);
	$cat_name = str_replace('__','_',$cat_name);
	return 'YOUR CATEGORY URL HERE!!' . $cat_name;
}
?>

Make sure that your blog still works. Replace the part that it says to replace with http://yoursite.com/category/.

6. Open up b2evocore/_class_item.php, and find this line:

$cat_name = '<a href="'.url_add_param( get_bloginfo('blogurl', $curr_blogparams), 'cat='.$cat_ID ).'" title="'.$link_title.'">'.$cat_name.'</a>';

Comment it out, and replace with this:

$cat_name = '<a href="'.category_stub_link($cat_name).'" title="'.$link_title.'">'.$cat_name.'</a>';

Now, you should have proper category links on each blog post. If you don't, stop and debug.

7. Open up skins/_categories.php, and find this line:

echo '<a href="'.url_add_param( get_bloginfo('blogurl'), 'cat='.$cat_ID ).'">'.format_to_output($cat['cat_name'], 'htmlbody').'</a> <span class="dimmed">('.$cat['cat_postcount'].')</span>';

Comment it out, and replace with this:

echo '<a href="'.category_stub_link($cat['cat_name']).'">'.format_to_output($cat['cat_name'], 'htmlbody').'</a> <span class="dimmed">('.$cat['cat_postcount'].')</span>';

Now, the category links in the sidebar of each skin should be cleaned, too.

All done! :)