Estimado , el codigo de paginado puedes incluirlo como un include , valga la redundancia , en todos los scripts , sino puedes hacer algo asi:
Código php:
Ver original<?php
include("Header.php");
?>
html
<?php
include("footer");
?>
Y dentro de footer el codigo de paginación , de ese modo te queda algo más prolija la implementación.
Saludos!