Te recomendaría usar el script:
Paginator (de Jpinedo).
http://jpinedo.webcindario.com/scripts/paginator/
Ahí veras fácilmente como usarlo en la práctica .. Por tu parte sólo tendrás que componer tu sentencia SQL tipo:
Código PHP:
$sql="SELECT * FROM tabla WHERE camp='".$_POST['buscar']."'";
Donde "buscar" será tu campo (input) de tu formulario (en method="POST") que enviaras a este script (si mismo u otro).
Y ese $sql darselo a la función correspondiente de "Paginator" para que este haga su tarabajo de paginado (con más opciones y controles de los que tu código propuesto hace).
Un saludo,