You are absolutely right, and I noticed this when I first implemented the paging. There is a feature in .NET 3.5 that makes it easy to make AJAX calls add to the browser history. But GSP targets .NET 2.0 so I couldn't take advantage of it.
There is a good chance the next major version of GSP will set .NET 3.5 as the required minimum, and I will be sure to add this.
Until then, those of you who like to play with source code can add it today if you are using .NET 3.5. I don't have the exact details for you, but I think you add a history point to the ScriptManager control each time a new page of albums is requested. I think it would be one line of code.
Roger Martin
Creator and Lead Developer of Gallery Server Pro