While building oldsoul.com.au we needed a way of staying within the Catalogue category and not get posts from the already sold items in the Portfolio category.
The site uses the included theme twentyeleven and the file to be changed is
<h3><?php _e( 'Post navigation', 'twentyeleven' ); ?></h3>
<span><?php previous_post_link( '%link', __( '<span>←</span> Previous', 'twentyeleven' ),TRUE ); ?></span>
<span><?php next_post_link( '%link', __( 'Next <span>→</span>', 'twentyeleven' ),TRUE ); ?></span>
</nav><!-- #nav-single -->
The previous_post_link() and next_post_link() can be set to stay within the same category if the third parameter is set to true as can be seen in the above example. The highlighted text is what needs to be added.