Is it possible to customize how my gallery shortcode works. eg. have a div for showing the image then a list of thumbnails at the bottom or side?
Or perhaps I can create a custom template file to loop through my page's gallery images?
You may complete override your gallery shortcode using the filter
You may iterarate through the image attached to your post to build your own gallery.
See the implementation of gallery shortcode here: http://core.trac.wordpress.org/browser/trunk/wp-includes/media.php#L758
EDIT: There are some plugins that modify the default behaviour of the gallery shortcode. Search it from the "Add New Plugin" of the backend. Use the string "gallery shortcodes".
Note: if you want you can use nextgen-gallery to manage your photos. It has numerous plugin to display with other gallery, like Smooth Gallery, Nivo Slider or jQuery cycle.
I would recommend the Attachments plugin instead of using the gallery, it uses the regular wordpress media library, but you can control the output much more easily. If you pair it up with add_image_size you can create a range of different thumbnails.