Pagination on a custom page template

This is what I do for paging. I hope it helps you get on the right track, it may be overkill for what you are trying to do…

First I set $paged:

$paged = ( get_query_var( 'paged' ) ) ? get_query_var( 'paged' ) : 1;

Then build your $args array, make sure to call in:

'paged' => $paged

Run your query including the needed functions for paging (this is a sample, change what you need to make it yours):

        //the query using arguments above
        $wp_query = new WP_Query( $args );

        //use the query for paging
        $wp_query->query_vars[ 'paged' ] > 1 ? $current = $wp_query->query_vars[ 'paged' ] : $current = 1;

        //set the "paginate_links" array to do what we would like it it. Check the codex for examples http://codex.wordpress.org/Function_Reference/paginate_links
        $pagination = array(
            'base' => @add_query_arg( 'paged', '%#%' ),
            //'format' => '',
            'showall' => false,
            'end_size' => 4,
            'mid_size' => 4,
            'total' => $wp_query->max_num_pages,
            'current' => $current,
            'type' => 'plain'
        );

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

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

        //run the query
        if ( $wp_query->have_posts() ) : while ( $wp_query->have_posts() ) : $wp_query->the_post();

All that’s left is to tell the page where you want the page links:

        //print the paging links to the page
        echo '<div class="pydPaging">' . paginate_links($pagination) . '</div>';

Again, this may be overkill, but it works well.