WordPress is good at taking care of pagination automatically if you are displaying all the posts. But incase if you have a custom query to retrieve results for example: all posts from a certain category then the default pagination does not display the next page of posts. Instead, it displays the same posts again. However, there is a way to get pagination (paging as some call it) with a custom query.
Following code will take care of the pagination:
$page = (get_query_var("paged")) ? get_query_var("paged") : 1;
$wp = new WP_Query();
$wp->query("category_name=CATEGORY_NAME&paged=$page");
while ($wp->have_posts()) : $wp->the_post();
<!-- Display your posts here -->
<?php endwhile;?>
Hetal Bhagat 
Thanks for posting this example. I tried and it worked perfectly. One thing I’m struggling with however is getting that example to display previous or next to work at all.
I tried previous_posts_link() and next_posts_link() and neither of them seem to work. I think because they want to work on the default $wp_query instead of the custom query.
Perhaps I’m missing something really basic?
Thanks for the comment. Nice to see if was helpful to you. The previous/next links works fine for me. Do you have more than 10 posts in that category? If it is less than that you might not see the paging. The number of posts to show can be configured in Settings (default is 10). You could also try the WP-Page Navi plugin if that helps.
Wow, I can’t thank you enough for this! Worked perfectly the first time around. You rock 🙂