If you have PHP and MySQL on your web server,
Gallery2 is the way to go if you are looking for a plug and play solution.
If you are of the more adventurous type, and are looking for a challenge, learn PHP (for server side scripting), MySQL (for server side database), XHTML, CSS, and possibly even AJAX and program your own photo gallery.