Otto has created a very thorough primer to create a WordPress photo gallery without a plugin. He walks you through understanding pictures and galleries, creating and modifying an image template, and tweaking image and thumbnail sizes.
He reminds us:
You don’t really need plugins to create photo galleries. WordPress has a huge amount of gallery functionality built right in. You just need to make your theme smarter in order to take advantage of it.
Click through to read Photo gallery primer on Otto on WordPress.