If you read the linked article you are missing the correct navigation call!
<div class="navigation">
<div class="alignleft"><?php previous_posts_link('? Previous') ?></div>
<div class="alignright"><?php next_posts_link('More ?') ?></div>
</div>
Also if you want page numbers [1] 2 3
instead of << Prev next >>
have a look at the plugin wp-page-navi
As you are using a query then you need to read this for wp-page-navi, it has more different paging code.
The other bit I would add for page navi is a test to see if the function exists.
<?php if( function_exists('wp_pagenavi') ) : ?>
<?php wp_pagenavi(); ?>
<?php else : ?>
<div class="navigation">
<div class="alignleft"><?php previous_posts_link('? Previous') ?></div>
<div class="alignright"><?php next_posts_link('Next ?') ?></div>
</div>
<?php endif; ?>
If you want another example then open the loop.php
file in the twenty ten theme and find the navigation blocks
<?php /* Display navigation to next/previous pages when applicable */ ?>
<?php if ( $wp_query->max_num_pages > 1 ) : ?>
<div id="nav-above" class="navigation">
<div class="nav-previous"><?php next_posts_link( __( '<span class="meta-nav">←</span> Older posts', 'twentyten' ) ); ?></div>
<div class="nav-next"><?php previous_posts_link( __( 'Newer posts <span class="meta-nav">→</span>', 'twentyten' ) ); ?></div>
</div><!-- #nav-above -->
<?php endif; ?>
Then open style.php and copy the styles you want!
HTH
David