Revisa como trabaja al respecto este script:
Paginator (de Jpinedo)
http://jpinedo.webcindario.com/scripts/paginator/
Ahí veras como propagar las variabels que el URL tenga (por GET o POST) + las tuyas que tu paginado necesita para hacer su trabajo. De hecho si quieres usarlo tal cual .. usalo, .. a veces no es necesario "re-inventar" la rueda.
Un saludo,