Customizing the WP Gallery

You have a couple of options:

1. You can create an image.php template file for your theme (copy single.php) and replace:

<div class="alignleft"><?php previous_post_link('&laquo; %link') ?></div>
<div class="alignright"><?php next_post_link('%link &raquo;') ?></div>

with

<div class="alignleft"><?php previous_image_link() ?></div>
<div class="alignright"><?php next_image_link() ?></div>

2. You can use a full blown gallery plugin like the NextGen gallery plugin

3. You can use a plugin that simply adds lightbox functionality to your existing wordpress galleries. The lighbox image views comes with next and previous links: Heres as few plugins/articles to get you started:
http://justintadlock.com/archives/2008/04/13/cleaner-wordpress-gallery-plugin
http://www.idratherbewriting.com/2008/07/10/wordpress-image-gallery-example/