How to get category/tag in URL for Pagination links?

Why can you not use the core functions previous_posts_link()/next_posts_link() or posts_nav_link(), all of which already account for the taxonomy archive context?

EDIT:

I think I understand your question now. You want pagination links, rather than previous/next page links.

WordPress also has a native function for pagination links: paginate_links() (Codex ref).

Here’s how I use this function in my own Theme:

function oenology_paginate_archive_page_links( $type="plain", $endsize = 1, $midsize = 1 ) {
    global $wp_query, $wp_rewrite;  
    $wp_query->query_vars['paged'] > 1 ? $current = $wp_query->query_vars['paged'] : $current = 1;

    // Sanitize input argument values
    if ( ! in_array( $type, array( 'plain', 'list', 'array' ) ) ) $type="plain";
    $endsize = (int) $endsize;
    $midsize = (int) $midsize;

    // Setup argument array for paginate_links()
    $pagination = array(
        'base' => @add_query_arg('page','%#%'),
        'format' => '',
        'total' => $wp_query->max_num_pages,
        'current' => $current,
        'show_all' => false,
        'end_size' => $endsize,
        'mid_size' => $midsize,
        'type' => $type,
        'prev_text' => '<<',
        'next_text' => '>>'
    );

    if( $wp_rewrite->using_permalinks() )
        $pagination['base'] = user_trailingslashit( trailingslashit( remove_query_arg( 's', get_pagenum_link( 1 ) ) ) . 'page/%#%/', 'paged' );

    if( !empty($wp_query->query_vars['s']) )
        $pagination['add_args'] = array( 's' => get_query_var( 's' ) );

    echo paginate_links( $pagination );
}