Hi,
if you want single-page pagination, you could use a jQuery plugin, for instance http://flaviusmatis.github.io/simplePagination.js/ . You can feed it your entire gallery and it will do the heavy lifting for you.
If you want multi-page pagination (where each page shows part of your gallery), you can use any simple php approach for pagination – and just query the part of the gallery you need on each page.
Unless you’re experienced with PHP, I suggest you take the first approach.