veo que muchos tienen problemas con el codigo de paginacion.
por esto el codigo: 
 Código PHP:
    <?
function Conectarse(){
   if (!($link=mysql_connect("localhost","USUARIO","CONTRASEÑA"))) 
    {
    echo "Error conectando a la base de datos."; 
    exit();
    }
    if (!mysql_select_db("base de datos",$link)) 
    {
    echo "Error seleccionando la base de datos.";
    exit();
    }
    return $link; 
}
$link=Conectarse(); 
$sql="SELECT * FROM registros "; // la consulta
$resultado_registros=mysql_query($sql,$link); // ejecuta la consulta
$cantidad_registros=mysql_num_rows($resultado_registros); // cantidad de registros
$registros_real=mysql_num_rows($resultado_regostros);  // cantidad de registros
$largo_pagina=0;
if($cantidad_registros>0){
    $largo_pagina=20; // largo que le quieres dar a los resultados
    if(isset($_GET['numpagina'])) {
        $numpagina=$_GET['numpagina'];
        $siguiente=(($numpagina-1)*$largo_pagina);
    }else{
        $siguiente=0;
        $numpagina=1;
    }
    $total_paginas=(($cantidad_registros/$largo_pagina));
    if((int)$total_paginas<$total_paginas){
        $total_paginas=(int)$total_paginas+1;
    }
    $sql = $sql." LIMIT $siguiente,$largo_pagina";    
    $result_clientes=mysql_query($sql,$link);
    $cantidad_registros=mysql_num_rows($result_clientes);
}
 
/**************************************************************************
 
 
el codigo de la tabla para mostrat los 20 resultados
 
 
**************************************************************************/
 
if($registros_real>$largo_pagina){
$anterior=$numpagina-1;
$proximo=$numpagina+1;
if($anterior<1){
    $anterior=1;
}
if($proximo>$total_paginas){
    $proximo=$total_paginas;
}
?>
<script>
function fnc_pagina(X){
    location.href="?ver=t&numpagina="+X;
    }
</script>
<table border="0" align="center" cellpadding="0" cellspacing="0">
 <tr> 
    <td align="center">Página <?=$numpagina;?> 
      de <?=$total_paginas?></td>
  </tr>
  <tr> 
<td align="center">
<a href="javascript:fnc_pagina('<?=$anterior?>');">
« Ver <?=$largo_pagina?> anteriores</a>
<span>|</span> 
<a href="javascript:fnc_pagina('<?=$proximo?>');">
Ver <?=$largo_pagina?> próximos »</a>
</td>
  </tr>
   <tr>
      <td>
<?
for($i=0; $i<$total_paginas; $i++){   // ESTO MUESTRA TODAS LAS PAGINAS EN NUMEROS EJEMPLO 1 2 3 4 5 6 7 8 9 ...
?>
    <a href="javascript:fnc_pagina('<?= $i+1?>');"><?= $i+1?></a><? }?> </td>
     </tr>
 </table>
<? }
mysql_free_result($resultado_registros); //LIBERAMOS LA MEMORIA
mysql_close($link); //CERRAMOS LA CONEXION
?>    
  
resultado:  

es simple no?.