This Wordpress plugin creates a simple widget that prints Previous and Next links. The number of posts (or pages) in either direction is given in parenthesis. This plugin also solves the ambiguity of posts in multiple categories.

<?php
/**
 * Plugin name: Simple Nav
 * Author: Joseph Burnett
 * Author URI: http://www.josephburnett.com
 * Plugin URI: http://www.josephburnett.com
 * Version: 1.0
 * Description: Adds a widget which will provide simple navigation links to adjacent posts (or pages).
 **/

class SimpleNav extends WP_Widget {

    private static $class_initialized = false;
    private static $simple_nav_category = null;
    private static $is_single = false;
    private static $is_category = false;

    private static $nav_initialized = false;
    private static $next_link = null;
    private static $next_count = 0;
    private static $prev_link = null;
    private static $prev_count = 0;
    
    # Initialize members used by entire class
    private static function init() {
        global $wp;

        error_log("DEBUG initializing");
        if (SimpleNav::$class_initialized == false) {
            if (is_single()) {
                SimpleNav::$is_single = true;
                SimpleNav::$is_category = false;
                SimpleNav::$simple_nav_category = SimpleNav::determine_post_category();
            }
            if (is_category() or !empty($wp->query_vars['s'])) {
                SimpleNav::$is_single = false;
                SimpleNav::$is_category = true;
                SimpleNav::$simple_nav_category = SimpleNav::determine_category();
            }
            SimpleNav::$class_initialized = true;
       }
    }

    # Initialize members used in rendering navigation
    private static function init_nav() {
        error_log("DEBUG initializing links");
        if ( !SimpleNav::$nav_initialized ) {
            error_log("DEBUG rendering links and finding counts");
            SimpleNav::$next_link = SimpleNav::get_link(false);
            SimpleNav::$next_count = SimpleNav::get_count(false);
            SimpleNav::$prev_link = SimpleNav::get_link(true);
            SimpleNav::$prev_count = SimpleNav::get_count(true);
            SimpleNav::$nav_initialized = true;
        }
    }

    # Widget constructor
    function SimpleNav() {
        parent::WP_Widget(false, $name = 'Simple Nav');
    }

    # Render the widget
    function widget($args, $instance) {

        SimpleNav::init();
        SimpleNav::init_nav();

        $prev_text = "Previous";
        $next_text = "Next";

        $right_arrow = "»";
        $left_arrow = "«";

        $prev_class = "simple_nav_prev";
        $next_class = "simple_nav_next";

        echo "<div class=\"simple_nav\">\n";

        if ( SimpleNav::$is_single ) {

            if ( !empty( SimpleNav::$prev_link ) )
                echo "<span class=\"$prev_class\"><a href=\"" . SimpleNav::$prev_link . "\">$left_arrow $prev_text (" . SimpleNav::$prev_count . ")</a></span>";

            if ( !empty( SimpleNav::$next_link ) )
                echo "<span class=\"$next_class\"><a href=\"" . SimpleNav::$next_link . "\">$next_text (" . SimpleNav::$next_count . ") $right_arrow</a></span>";
        }

        if ( SimpleNav::$is_category ) {

            if ( !empty( SimpleNav::$prev_link ) ) {
                if ( SimpleNav::$prev_count == 1 )
                    echo "<span class=\"$prev_class\"><a href=\"" . SimpleNav::$prev_link . "\">$left_arrow $prev_text (" . SimpleNav::$prev_count . " page)</a></span>";
                else
                    echo "<span class=\"$prev_class\"><a href=\"" . SimpleNav::$prev_link . "\">$left_arrow $prev_text (" . SimpleNav::$prev_count . " pages)</a></span>";
            }

            if ( !empty( SimpleNav::$next_link ) ) {
                if ( SimpleNav::$next_count == 1 )
                    echo "<span class=\"$next_class\"><a href=\"" . SimpleNav::$next_link . "\">$next_text (" . SimpleNav::$next_count . " page) $right_arrow</a></span>";
                else
                    echo "<span class=\"$next_class\"><a href=\"" . SimpleNav::$next_link . "\">$next_text (" . SimpleNav::$next_count . " pages) $right_arrow</a></span>";
            }
        }

        echo "</div>\n";
    }

    # Update the instance of the widget
    function update($new_instance, $old_instance) {				
        return $old_instance; // nothing to do
    }

    # Print the form to configure the widget
    function form($instance) {
        echo "<p>A simple set of navigation links to the adjacent posts (or pages). ";
        echo "The number of posts (or pages) in either direction is given in parenthesis.</p>";
    }

    # Determine which category we're viewing
    private static function determine_category() {
        global $wp;
        return $wp->query_vars['category_name'];
    }

    # Determine which single category (of possibily many) we are navigating within
    private static function determine_post_category() {
        global $post, $wp;

        # Get the current post id
        $post_id = $wp->query_vars['p'];

        if ( empty( $post_id ) ) {
            error_log("DEBUG couldn't get current post id");
            return '';
        }

        # Get categories for the current post
        error_log("DEBUG finding categories for post " . $post_id);
        $post_categories = wp_get_post_categories( $post_id );
        $cats = array();
        $cat_slugs = array();
        foreach($post_categories as $c){
            $cat = get_category( $c );
            $cats[] = array( 'name' => $cat->name, 'slug' => $cat->slug, 'id' => $cat->term_id );
            $cat_slugs[] = $cat->slug;
            error_log("DEBUG adding category: " . $cat->slug);
        }

        if (count($cats) < 1) {
            # Post has no categories, so can't have a simple previous and next
            error_log("DEBUG post has no categories, returning empty");
            return '';
        }

        # What's the category we should be working in?
        $simple_nav_category = $wp->query_vars['simple_nav_category'];
        
        if ( !in_array($simple_nav_category, $cat_slugs) ) {
            # Current post doesn't have the given category, so we ignore it
            error_log("DEBUG post doesn't have given category, ignoring " . $simple_nav_category);
            $simple_nav_category = '';
        }
        
        if ( empty( $simple_nav_category ) ) {
            # No category was specified, so choose the first one
            $simple_nav_category = $cats[0]['slug'];
            error_log("DEBUG no simple_nav_category given, choosing " . $simple_nav_category);
        }

        error_log("DEBUG returning simple nav category: " . $simple_nav_category);
        return $simple_nav_category;
    }

    # Get a link to an adjacent object
    private static function get_link($prev = true) {

        $link = null;

        if ( SimpleNav::$is_single ) {
            $post = SimpleNav::adjacent_post( $prev, false );
            if ( !empty( $post ) )
                $link = get_permalink( $post->ID );
        }

        if ( SimpleNav::$is_category ) {
            $link = SimpleNav::adjacent_page_link( $prev );
        }

        return $link;
    }

    # Get a count of adjacent objects
    private static function get_count($prev = true) {

        $count = null;

        if ( SimpleNav::$is_single )
            $count = SimpleNav::adjacent_post( $prev, true );

        if ( SimpleNav::$is_category )
            $count = SimpleNav::adjacent_page_count( $prev ); 

        return $count;
    }

    # Get link to adjacent page of posts
    private static function adjacent_page_link($previous = true, $count_only = false) {
        global $wp_query;

        $current_page = max( 1, get_query_var('paged') );
        $last_page = max( 1, $wp_query->max_num_pages );

        error_log("DEBUG current page: " . $current_page);
        error_log("DEBUG last page: " . $last_page);

        $link = null;

        if ( $previous ) {

            if ( $current_page > 1 )
                $link = get_pagenum_link( $current_page - 1 );

        } else {

            if ( ($last_page - $current_page + 1) > 1 )
                $link = get_pagenum_link( $current_page + 1 );

        }

        error_log("DEBUG returning adjacent page link: " . $link);
        return $link;
    }

    # Get count of adjacent pages of posts
    private static function adjacent_page_count($previous = true, $count_only = false) {
        global $wp_query;

        $current_page = max( 1, get_query_var('paged') );
        $last_page = max( 1, $wp_query->max_num_pages );

        error_log("DEBUG current page: " . $current_page);
        error_log("DEBUG last page: " . $last_page);

        $count = 0;

        if ( $previous ) {

            if ( $current_page > 1 )
                $count = $current_page - 1;

        } else {

            if ( ($last_page - $current_page + 1) > 1 )
                $count = $last_page - $current_page;

        }

        error_log("DEBUG return adjacent page count: " . $count);
        return $count;
    }

    # Get information about adjacent posts
    private static function adjacent_post($previous = true, $count_only = false) {
        global $post, $wpdb;

        if ( empty( SimpleNav::$simple_nav_category ) ) {
            error_log("DEBUG couldn't determine simple_nav_category");
            return null;
        }

        # Build the SQL query
        $op = $previous ? '<' : '>';
        $current_post_date = $post->post_date;
        $order = $previous ? 'DESC' : 'ASC';

        $query  = "SELECT " . ($count_only ? "count(*)" : "p.*") . " FROM $wpdb->posts AS p ";
        $query .= "INNER JOIN $wpdb->term_relationships AS tr ON p.ID = tr.object_id ";
        $query .= "INNER JOIN $wpdb->term_taxonomy AS tt ON tr.term_taxonomy_id = tt.term_taxonomy_id ";
        $query .= "INNER JOIN $wpdb->terms AS t ON tt.term_id = t.term_id ";
        $query .= "WHERE p.post_date $op '%s' ";
        $query .= "AND p.post_type = 'post' ";
        $query .= "AND p.post_status = 'publish' ";
        $query .= "AND tt.taxonomy = 'category' ";
        $query .= "AND t.slug = '%s' ";
        if (!$count_only) {
            $query .= "ORDER BY p.post_date $order ";
            $query .= "LIMIT 1";
        }
        
        $prepared_query = $wpdb->prepare($query, $current_post_date, SimpleNav::$simple_nav_category);

        error_log("DEBUG " . $prepared_query);

        # Look for a cache hit
        $query_key = 'adjacent_post_' . md5($query);
        $result = wp_cache_get($query_key, 'counts');
        if ( false !== $result )
            return $result;

        # Cache miss
        if ($count_only) {
            $result = $wpdb->get_var($prepared_query);
            if ( empty( $result ) )
                $result = 0; // empty results means a count of zero
        } else {
            $result = $wpdb->get_row($prepared_query);
        }
        if ( null === $result ) {
            error_log("DEBUG nothing returned from query");
            $result = '';
        }

        # Cache the result
        wp_cache_set($query_key, $result, 'counts');
        return $result;
    }
    
    # Update a post link with the current simple nav category
    public static function post_link($permalink) {

        SimpleNav::init();

        if ( empty( SimpleNav::$simple_nav_category ) ) {
            error_log("DEBUG not adding simple_nav_category to permalink");
            return $permalink;
        } else {
            error_log("DEBUG adding simple_nav_category to permalink: " . SimpleNav::$simple_nav_category);
            return $permalink . "&simple_nav_category=" . SimpleNav::$simple_nav_category;
        }
    }
}

# Register the widget
add_action('widgets_init', create_function('', 'register_widget("SimpleNav");'));

# Add the simple_nav_category url parameter
add_filter('query_vars', 'add_simple_nav_category');
function add_simple_nav_category( $qvars ) {
    $qvars[] = 'simple_nav_category';
    return $qvars;
}

# Hook into the post_link filter
add_action('post_link', array('SimpleNav', 'post_link'));

?>