The easiest method I found to add a good pagination:
1. Install WP-PageNavi plugin.
2. In the template file, the loop should be like this:
<?php
// The Query,
$the_query = new WP_Query( 'category_name=blog&paged='.$paged );
// The Loop which loops through all the posts of category
while ( $the_query->have_posts() ) : $the_query->the_post();
?>
<?php the_content(); ?>
<?
endwhile;
//call wp-pagenavi plugin
wp_pagenavi( array('query' =>$the_query ));
// Reset Post Data
wp_reset_postdata();
?>
3. Change how many posts do you want to display per page in the admin, Settigs/Reading/Blog pages show at most.
That’s it, very easy to implement.


