Bueno de paginadores ya se ha hablado mucho, si quieres uno facil de implementar mira este excelente paginador con PHP OO solo pasale unos pocos paramentros y lo tenes funcionando al pelo.
http://objetivophp.com/?p=183 Mi amigo Marcelo de Objetivo PHP desarrollo esta increible clase.
Cualquier cosa pregunta!!