In the 2.0 beta release, the album_search.tpl file is broken in that it only shows the first n pictures, usually 20.
It shows L_NRESULTS when it should display N_TRESULTS as the total number of images found, and doesn't include the PAGINATION links.
Fix them and you have a multipage result set as provided by album_search.php
While I have done this with my own template, I'm not quite sure how to do it with the default or other templates. Perhaps someone else can jump in?
[Edit] Moved to the bugs tracker [/Edit]