Here is one solution for your sidebar. It should work for most themes and situations. There are some limitations of this method mostly having to do with it not rewinding the post counter on multi-loop pages.
Just stick the code in the sidebar, change the number of posts per category displayed and give it a shot. There are other ways to accomplish this and some different ways of handling multiple categories but this should give you a good start:
//if on single page
if ( is_single() ) :
//setup post data
global $post;
//get the category(s) of current post
$categories = get_the_category();
//loop through each category the post belongs too
foreach ($categories as $category) :
?>
//print category title
<li class="sidebar_links">
<h2>Recent <?php echo $category->name; ?> Posts</h2>
<ul>
<?php
//how many other posts from each of the current posts category
$posts = get_posts('numberposts=5&category='. $category->term_id);
//loop through posts
foreach($posts as $post) :
?>
//print post links
<li>
<a href="<?php the_permalink(); ?>" class="sidebar_link"><?php the_title(); ?>
</a>
</li>
//end posts loop
<?php endforeach; ?>
</ul>
</li>
<?php
//end categories loop
endforeach; endif ; ?>
-Aaron
wpcast.com (coming soon)