No interesse de não reinventar a roda, você pode querer verificar esta simples classe de paginação PHP:

http://www.catchmyfame.com/ 28/07/2007/finally-the-simple-pagination-class/

Provavelmente não será perfeito para você, mas é muito fácil modificar e voltar a codificar coisas muito mais interessantes do que paginação :)