The Problem

By default, in any given context, WordPress uses the main query to determine pagination. The main query object is stored in the $wp_query global, which is also used to output the main query loop:

if ( have_posts() ) : while ( have_posts() ) : the_post();

When you use a custom query, you create an entirely separate query object:

$custom_query = new WP_Query( $custom_query_args );

And that query is output via an entirely separate loop:

if ( $custom_query->have_posts() ) : 
    while ( $custom_query->have_posts() ) : 
        $custom_query->the_post();

But pagination template tags, including previous_posts_link(), next_posts_link(), posts_nav_link(), and paginate_links(), base their output on the main query object, $wp_query. That main query may or may not be paginated. If the current context is a custom page template, for example, the main $wp_query object will consist of only a single post – that of the ID of the page to which the custom page template is assigned.

If the current context is an archive index of some sort, the main $wp_query may consist of enough posts to cause pagination, which leads to the next part of the problem: for the main $wp_query object, WordPress will pass a paged parameter to the query, based on the paged URL query variable. When the query is fetched, that paged parameter will be used to determine which set of paginated posts to return. If a displayed pagination link is clicked, and the next page loaded, your custom query won’t have any way to know that the pagination has changed.

The Solution

Passing Correct Paged Parameter to the Custom Query

Assuming that the custom query uses an args array:

$custom_query_args = array(
    // Custom query parameters go here
);

You will need to pass the correct paged parameter to the array. You can do so by fetching the URL query variable used to determine the current page, via get_query_var():

get_query_var( 'paged' );

You can then append that parameter to your custom query args array:

$custom_query_args['paged'] = get_query_var( 'paged' ) 
    ? get_query_var( 'paged' ) 
    : 1;

Note: If your page is a static front page, be sure to use page instead of paged as a static front page uses page and not paged. This is what you should have for a static front page

$custom_query_args['paged'] = get_query_var( 'page' ) 
    ? get_query_var( 'page' ) 
    : 1;

Now, when the custom query is fetched, the correct set of paginated posts will be returned.

Using Custom Query Object for Pagination Functions

In order for pagination functions to yield the correct output – i.e. previous/next/page links relative to the custom query – WordPress needs to be forced to recognize the custom query. This requires a bit of a “hack”: replacing the main $wp_query object with the custom query object, $custom_query:

Hack the main query object

1. Backup the main query object: $temp_query = $wp_query
2. Null the main query object: $wp_query = NULL;

3. Swap the custom query into the main query object: $wp_query = $custom_query;

   $temp_query = $wp_query;
   $wp_query   = NULL;
   $wp_query   = $custom_query;
   

This “hack” must be done before calling any pagination functions

Reset the main query object

Once pagination functions have been output, reset the main query object:

$wp_query = NULL;
$wp_query = $temp_query;

Pagination Function Fixes

The previous_posts_link() function will work normally, regardless of pagination. It merely determines the current page, and then outputs the link for page - 1. However, a fix is required for next_posts_link() to output properly. This is because next_posts_link() uses the max_num_pages parameter:

<?php next_posts_link( $label , $max_pages ); ?>

As with other query parameters, by default the function will use max_num_pages for the main $wp_query object. In order to force next_posts_link() to account for the $custom_query object, you will need to pass the max_num_pages to the function. You can fetch this value from the $custom_query object: $custom_query->max_num_pages:

<?php next_posts_link( 'Older Posts' , $custom_query->max_num_pages ); ?>

Putting it all together

The following is a basic construct of a custom query loop with properly functioning pagination functions:

// Define custom query parameters
$custom_query_args = array( /* Parameters go here */ );

// Get current page and append to custom query parameters array
$custom_query_args['paged'] = get_query_var( 'paged' ) ? get_query_var( 'paged' ) : 1;

// Instantiate custom query
$custom_query = new WP_Query( $custom_query_args );

// Pagination fix
$temp_query = $wp_query;
$wp_query   = NULL;
$wp_query   = $custom_query;

// Output custom query loop
if ( $custom_query->have_posts() ) :
    while ( $custom_query->have_posts() ) :
        $custom_query->the_post();
        // Loop output goes here
    endwhile;
endif;
// Reset postdata
wp_reset_postdata();

// Custom query loop pagination
previous_posts_link( 'Older Posts' );
next_posts_link( 'Newer Posts', $custom_query->max_num_pages );

// Reset main query object
$wp_query = NULL;
$wp_query = $temp_query;

Addendum: What About query_posts()?

query_posts() for Secondary Loops

If you’re using query_posts() to output a custom loop, rather then instantiating a separate object for the custom query via WP_Query(), then you’re _doing_it_wrong(), and will run into several problems (not the least of which will be pagination issues). The first step to resolving those issues will be to convert the improper use of query_posts() to a proper WP_Query() call.

Using query_posts() to Modify the Main Loop

If you merely want to modify the parameters for the main loop query – such as changing the posts per page, or excluding a category – you may be tempted to use query_posts(). But you still shouldn’t. When you use query_posts(), you force WordPress to replace the main query object. (WordPress actually makes a second query, and overwrites $wp_query.) The problem, though, is that it does this replacement too late in the process to update the pagination.

The solution is to filter the main query before posts are fetched, via the pre_get_posts hook.

Instead of adding this to the category template file (category.php):

query_posts( array(
    'posts_per_page' => 5
) );

Add the following to functions.php:

function wpse120407_pre_get_posts( $query ) {
    // Test for category archive index
    // and ensure that the query is the main query
    // and not a secondary query (such as a nav menu
    // or recent posts widget output, etc.
    if ( is_category() && $query->is_main_query() ) {
        // Modify posts per page
        $query->set( 'posts_per_page', 5 ); 
    }
}
add_action( 'pre_get_posts', 'wpse120407_pre_get_posts' );

Instead of adding this to the blog posts index template file (home.php):

query_posts( array(
    'cat' => '-5'
) );

Add the following to functions.php:

function wpse120407_pre_get_posts( $query ) {
    // Test for main blog posts index
    // and ensure that the query is the main query
    // and not a secondary query (such as a nav menu
    // or recent posts widget output, etc.
    if ( is_home() && $query->is_main_query() ) {
        // Exclude category ID 5
        $query->set( 'category__not_in', array( 5 ) ); 
    }
}
add_action( 'pre_get_posts', 'wpse120407_pre_get_posts' );

That way, WordPress will use the already-modified $wp_query object when determining pagination, with no template modification required.

When to use what function

Research this question and answer and this question and answer to understand how and when to use WP_Query, pre_get_posts, and query_posts().