Theme Option not Working Inside a Function

1) Move the function to the functions.php file, that’s where it belongs. Put it at the end before any closing ?>:

function my_theme_navigation() 
{ 
    global $shortname;

    if( get_option( $shortname . '_next_prev_or_paginate' ) == 'Next' ) : 
        // the block for next-prev navigation 
        previous_posts_link ('Newer');
        next_posts_link('Older');
    else : 
        // the block for pagination
        global $wp_query; 
        $big = 999999999; // need an unlikely integer       
        echo paginate_links( 
            array( 
                'base' => str_replace( $big, '%#%', get_pagenum_link( $big ) ), 
                'format' => '?paged=%#%', 
                'current' => max( 1, get_query_var('paged') ), 
                'total' => $wp_query->max_num_pages 
            ) 
        ); 
    endif; 
}

2) Looks like the only thing you’re missing is the function call, that will print the navigation.
Not very familiar with archives.php, so using single.php as example:

<?php
/**
 * The Template for displaying all single posts.
 *
 * @package WordPress
 * @subpackage Twenty_Eleven
 * @since Twenty Eleven 1.0
 */

get_header(); ?>

        <div id="primary">
            <div id="content" role="main">

                <?php while ( have_posts() ) : the_post(); ?>

                    <nav id="nav-single">
                    <?php my_theme_navigation(); /* CALLING THE FUNCTION TO ECHO THE NAVIGATION */ ?>
                    </nav><!-- #nav-single -->

                    <?php get_template_part( 'content', 'single' ); ?>

                    <?php comments_template( '', true ); ?>

                <?php endwhile; // end of the loop. ?>

            </div><!-- #content -->
        </div><!-- #primary -->

<?php get_footer(); ?>

---

Original answer

Hypothesis

If, as the question says,

this code is displaying Next/Previous links at all times

^{(My emphasis)} It much probably means that the if/else
is not working.

---

Option Value

Supposing $shortname is equal to "shortname", I created an option in the table wp_options.

---

Test

Putting this code in header.php, inside <div id="main"> from TwentyEleven:

function my_theme_navigation() { 
  if( 'Next' == get_option( 'shortname_next_prev_or_paginate' ) ) : 
      // the block for next-prev navigation 
      echo 'Previous/Next selected.';
  else : 
      // the block for pagination
      echo 'Pagination selected.';
  endif; 
}
my_theme_navigation();

---

Result and Possible Solution

It does echo correctly when the option value is manually changed in the database.

Make sure the following functions/commands are working in this order:

1. get_option, does it grabs the value? The value exists in the database?
2. paginate_links, does it prints correctly if called alone? Without get_option and if/else?
3. if/else, if the previous are working this one gotta be working