Pues yo te recomiendo utilizar PHPPaging 2.0,
Yo lo utilizo en mi web y me va de lo mejor, aqui enlace:
http://phppaging.phperu.net/
esta muy bien documentado, ejemplos y esta chevere por que puedes integrarlo con SEO, y personalizarlo de muchas formas, alli veras que es muy buena, ya te dije te la recomiendo.
