Well the simplest way I can think of is something like this…
<ul class="categories">
<?php
$categories = get_categories(); //can add parameters here to swtich the order, etc;
if(!empty(categories)):
foreach($categories as $i => $category):
?>
<li class="category">
<span><?php echo $category->name ?></span>
<?php
query_posts('posts_per_page=-1&cat=" . $category->term_id);
if ( have_posts() ) :
?>
<ul class="posts">
<?php
while ( have_posts() ) : the_post(); //we make a loop for each category,
?>
<li class="post">
<a href="https://wordpress.stackexchange.com/questions/5270/<?php the_permalink();?>"><?php the_title();?></a>
</li>
<?php endwhile; ?>
</ul>
<?php endif; ?>
<?php wp_reset_query(); ?>
</li>
<?php endforeach; endif; ?>
</ul>
Warning: this is untested code, but it should work just fine. (Just add it to your sidebar.php file or wherever you generate your sidebar.)