This is the code I use. It grabs all of the related posts to the category that post is in and the code goes right into the sidebar, so outside the loop:

<?php
if ( is_single() ) :
global $post;
$categories = get_the_category();
foreach ($categories as $category) :
$posts = get_posts('numberposts=4&exclude=' . $GLOBALS['current_id'] . '&category='. $category->term_id);
//To change the number of posts, edit the 'numberposts' parameter above
if(count($posts) > 1) {
?>


<div class="widget more-category">
<h3 class="widgettitle">More in <?php echo $category->name; ?></h3>
<ul>
<?php foreach($posts as $post) : ?>
<li><a href="<?php the_permalink(); ?>"><?php the_title(); ?></a></li>
<?php endforeach; ?>
</ul>
</div>

<?php } ?>


Hope this helps! :)