I have been using Picasa for a while to organize my photos on my machine, run a local slideshow, etc. It is a good software for that. I generate my photo albums with the HTML export facility of Picasa which also has a simple template system that lets you adapt the output.
web\templates directory of your Picasa installation, and that is it. Picasa will pick up the template automatically from this directory.
Not all my albums use the cleaned up version yet, but you can look at, say, my photos of Amsterdam as an example (I have commented out the copyright statement and the extra calligraphy image from the distribution, you might want to adapt it to your taste…).
Having said that, I will also have to look at my photos on Picasa Web again now; they have just made it possible for international users to buy (if necessary) additional disc space. This facility has some nice features, it may very well be a nice alternative to my current, mostly manual way of generating albums on the Web. I do not know yet.