Load posts into sidebar and paginate via ajax?

Is it possible to paginate, or load the next / previous posts in the sidebar without messing with the entire page pagination? Such as AJAX?

Right now I’m querying custom post type posts to load the latest 2 posts, and need to load the next or previous in it’s place.

Any Ideas?

EDIT: I tried Bainternet’s suggestion but still can’t get it to work.

I put this in my sidebar exactly as shown:

<?php $args = array('posts_per_page' => 1);
$sidebar = new WP_Query($args); 
if ( $sidebar->have_posts() ) : 
    while ( $sidebar->have_posts() ) : $sidebar->the_post(); ?>
        <div class="story">
            <a href="<?php the_permalink(); ?>" title="<?php the_title(); ?>"><?php the_title(); ?></a>
        </div>

    <?php endwhile; 
 endif; ?>
    <span class="more_links"></span>
    <span class="get_more">
    <input type="hidden" name="offset" id="offset" value="1">
    <input type="submit" name="more" id="more" value="Get more links">
    </span>
    <script type="text/javascript" >
    $(document).ready(function($) {
        $('#more').click(function() { 
            var data = {
                action: 'more_links',
                offset: $( '#offset' ).val(),
                _ajax_nonce: <?php echo wp_create_nonce( 'more_links' ); ?>
            };
            // since 2.8 ajaxurl is always defined in the admin header and points to admin-ajax.php
            $.post(ajaxurl, data, function(response) {
                var res = wpAjax.parseAjaxResponse(response, 'ajax-response');
                $.each( res.responses, function() { 
                    if (this.what == 'has') {
                        //insert links
                        $(".more_links").append( this.data.html ); 
                        //update offset value
                        $("#offset").val(this.data.offset);
                        $(".more_links").fadeIn("fast");
                    }else{
                        //no more links found
                        $(".more_links").append( this.data.html );
                        $(".get_more").remove();
                    }
                    //end if
                    });//end each
            });
            return false;
        })
    });
    </script>

And this in my functions:

add_action('wp_ajax_nopriv_more_links', 'my_AJAX_more_links_function');

function my_AJAX_more_links_function(){
check_ajax_referer('more_links');
$success_response = new WP_Ajax_Response();
$args = array('posts_per_page' => 1 , 'offset' => $_POST['offset']);
$sidebar = new WP_Query($args);
if ( $sidebar->have_posts() ){ 
     while ( $sidebar->have_posts() ) {
        $sidebar->the_post(); 
        $out .= '<div class="story">';
        $out .= '<a href="'.the_permalink().'" title="'. the_title.'">'.the_title().'</a></div>';
    }
    $success_response->add(array(
                'what' => 'has',
                'data' => array('html' => $out, 'offset' => $_POST['offset'])
    ));
}else{
    $out = __('Sorry but No more!');
    $success_response->add(array(
                'what' => 'none',
                'data' => $out
            ));
}
$success_response->send();      
exit;   
}
add_action('wp_head','add_scripts_121');
function add_scripts_121(){
wp_enqueue_script('wp-ajax-response');
}