I just did this the other night, it is really easy. I used this site as a referece:
While this is not going to be what everyone would want, it gives you the idea.
A couple hints, I had been using the "Page" feature in 1.5, so if you havent created a "Page" do that, then go to it, view the source and compare your source to what he is describing in his article.
You will need to play with the CSS file. The directions in his article don't show the proper width to change to and so forth.
I am using the default theme at http://www.jaygietl.com and I have a link on the right sidebar for my photots. So you can see that I was successful in integrating the style to the Gallery.