Where to call my pagination function?

If you added the pagination() function to your functions.php, you only have to call it in your theme files. Which file depends on where you want to display it, see the Template Hierarchy for details.

You don’t want to call this inside The Loop (between the while () {} or while : ... endwhile;), because this will display it for each post again. Whether you then call it in your search.php or loop-search.php depends on your personal preference. Twenty Ten does it in the loop*.php files. Summarized, it would look like this:

<!-- Display pagination links above the posts -->
<?php pagination(); ?>
<!-- Display the posts -->
<?php if(have_posts()) { while(have_posts()) { the_post();?>
<!-- Some details for this post -->
<!-- End the loop -->
<?php }} /* if, while */ ?>
<!-- Display pagination links again below the posts -->
<?php pagination(); ?>

I recommend you to prefix the name of the pagination() function with something more unique. You never know when WordPress will include a function called pagination() itself. dan_pagination() is a possible alternative 🙂

There are many pagination tutorials on the web, and many of them contain inaccuracies. So does the tutorial you linked to. Instead of using the total number of posts of the current query, it will count all posts in the blog to determine the number of pages. This will give errors on search pages. I would change the start of the function like this:

function wpse18805_pagination( $scope = 2 ) {
    global $wp_query;

    $numPages = $wp_query->max_num_pages;
    $curPage = $wp_query->get( 'paged' );
    if ( ! $curPage ) {
        $curPage = 1;
    }

    // page bounds ... continue from there

This function will also generate links that always start counting from the base of the blog, so it won’t work for search pages. To fix that, replace the line after // echo the link with:

echo '<li><a href="' . get_pagenum_link( $page ) . '">' . $page . '</a></li>';