I used
jalbum software. It's a free download, and fully customizable. It takes some time (and a little programming knowledge) to edit the "skin" to achieve the look you want, but once it's done, creating new galleries is simple.
I hosted mine on a different website (
ocusafe.com) just because I find it easier to upload an entire folder via Dreamweaver than to upload several files within folders through the

ftp setup. But I don't see why it couldn't be hosted on a

store.
Ultimately, I would prefer to see the

gallery modified to look like this, but until that happens, this works for me.