Pues yo tengo una paginacion hecha, muestro de hasta 5 filas de una tabla como máximo en una tablalo puse así
 
Esto lo tengo fuera del html 
 Código PHP:
    <?php
$num = 5;
$comienzo=$_REQUEST['comienzo'];
     if (!isset($comienzo)) 
    $comienzo = 0;
?>    
  Y luego al final de la tabla  
 Código PHP:
    <?php
if ($comienzo > 0)
               print ("[ <A HREF='$_SERVER[PHP_SELF]?comienzo=" . ($comienzo - $num) . "'>Anterior</A> | ");
            else
               print ("[ Anterior | ");
            if ($nfilas > ($comienzo + $num))
               print ("<A HREF='$_SERVER[PHP_SELF]?comienzo=" . ($comienzo + $num) . "'>Siguiente</A> ]\n");
            else
                print ("Siguiente ]\n");
?>    
  Si te vale, lo que hace es mostrar como e dicho 5 de las filas de mi base de datos.