Kaiser's answer is awesome and thorough, however just changing the ORDER BY clause isn't enough unless your menu_order matches your chronological order.

I can't take credit for this, but I found the following code in this gist:

<?php
/**
 * Customize Adjacent Post Link Order
 */
function wpse73190_gist_adjacent_post_where($sql) {
  if ( !is_main_query() || !is_singular() )
    return $sql;
  
  $the_post = get_post( get_the_ID() );
  $patterns = array();
  $patterns[] = '/post_date/';
  $patterns[] = '/\'[0-9]{4}-[0-9]{2}-[0-9]{2} [0-9]{2}:[0-9]{2}:[0-9]{2}\'/';
  $replacements = array();
  $replacements[] = 'menu_order';
  $replacements[] = $the_post->menu_order;
  return preg_replace( $patterns, $replacements, $sql );
}
add_filter( 'get_next_post_where', 'wpse73190_gist_adjacent_post_where' );
add_filter( 'get_previous_post_where', 'wpse73190_gist_adjacent_post_where' );
 
function wpse73190_gist_adjacent_post_sort($sql) {
  if ( !is_main_query() || !is_singular() )
    return $sql;
  
  $pattern = '/post_date/';
  $replacement = 'menu_order';
  return preg_replace( $pattern, $replacement, $sql );
}
add_filter( 'get_next_post_sort', 'wpse73190_gist_adjacent_post_sort' );
add_filter( 'get_previous_post_sort', 'wpse73190_gist_adjacent_post_sort' );

I've modified the function names for WP.SE.

If you only change the ORDER BY clause, the query still looks for posts greater than or less than the current post date. If your posts aren't in chronological order, you won't get the right post.

This changes the where clause to look for posts where the menu_order is greater than or less than the current post's menu_order, in addition to modifying the orderby clause.

The orderby clause also shouldn't be hardcoded to use DESC as it will need to switch based on whether you are getting the next or previous post link.

Kaiser's answer is awesome and thorough, however just changing the ORDER BY clause isn't enough unless your menu_order matches your chronological order.

I can't take credit for this, but I found the following code in this gist:

<?php
/**
 * Customize Adjacent Post Link Order
 */
function wpse73190_gist_adjacent_post_where($sql) {
  if ( !is_main_query() || !is_singular() )
    return $sql;
  
  $the_post = get_post( get_the_ID() );
  $patterns = array();
  $patterns[] = '/post_date/';
  $patterns[] = '/\'[0-9]{4}-[0-9]{2}-[0-9]{2} [0-9]{2}:[0-9]{2}:[0-9]{2}\'/';
  $replacements = array();
  $replacements[] = 'menu_order';
  $replacements[] = $the_post->menu_order;
  return preg_replace( $patterns, $replacements, $sql );
}
add_filter( 'get_next_post_where', 'wpse73190_gist_adjacent_post_where' );
add_filter( 'get_previous_post_where', 'wpse73190_gist_adjacent_post_where' );
 
function wpse73190_gist_adjacent_post_sort($sql) {
  if ( !is_main_query() || !is_singular() )
    return $sql;
  
  $pattern = '/post_date/';
  $replacement = 'menu_order';
  return preg_replace( $pattern, $replacement, $sql );
}
add_filter( 'get_next_post_sort', 'wpse73190_gist_adjacent_post_sort' );
add_filter( 'get_previous_post_sort', 'wpse73190_gist_adjacent_post_sort' );

I've modified the function names for WP.SE.

If you only change the ORDER BY clause, the query still looks for posts greater than or less than the current post date. If your posts aren't in chronological order, you won't get the right post.

This changes the where clause to look for posts where the menu_order is greater than or less than the current post's menu_order, in addition to modifying the orderby clause.

The orderby clause also shouldn't be hardcoded to use DESC as it will need to switch based on whether you are getting the next or previous post link.