Tienes un buen ejemplo en la siguiente web:
http://programacion.com/php/codigo/34/
Te voy a poner el código que aparece en esa página para explicártelo, aunque es muy sencillo de entender:
<html>
<head>
<title>Páginación de resultados</title>
</head>
<body bgcolor=#FFFFFF>
<?
// Datos de conexión a la base
$base=\"nombredelabase\";
$con=mysql_connect(servidor,usuario,password);
mysql_select_db($base,$con);
if (!isset($pg))
$pg = 0; // $pg es la pagina actual
$cantidad=10; // cantidad de resultados por página
$inicial = $pg * $cantidad;
$pegar = \"SELECT * FROM tabla ORDER BY titulo LIMIT $inicial,$cantidad\";
$cad = mysql_db_query($base,$pegar) or die (mysql_error());
$contar = \"SELECT * FROM tabla ORDER BY titulo\";
$contarok= mysql_db_query($base,$contar);
$total_records = mysql_num_rows($contarok);
$pages = intval($total_records / $cantidad);
// Imprimiendo los resultados
while($array = mysql_fetch_array($cad)) {
echo $array[\'titulo\'].\"<br>\";
}
// Cerramos la conexión a la base
$con=mysql_close($con);
// Creando los enlaces de paginación
echo \"<p>\";
if ($pg <> 0)
{
$url = $pg - 1;
echo \"<a href=\'paginar.php?pg=\".$url.\"\'>« Anterior</a> \";
}
else {
echo \" \";
}
for ($i = 0; $i<($pages + 1); $i++) {
if ($i == $pg) {
echo \"<font face=Arial size=2 color=ff0000><b> $i </b></font>\";
}
else {
echo \"<a href=\'paginar.php?pg=\".$i.\"\'>\".$i.\"</a> \";
}
}
if ($pg < $pages) {
$url = $pg + 1;
echo \"<a href=\'paginar.php?pg=\".$url.\"\'>Siguiente »</a>\";
}
else {
echo \" \";
}
echo \"</p>\";
?>
</body>
</html>
Primero conectas con la base de datos. Se van a mostrar páginas de 10 resultados, aunque lo puedes variar modificando una variable. Debes tener una variable con el número de página que quieres mostrar. Luego se calcula a partir de esa variable los resultados a mostrar y se obtienen de la base de datos usando una consulta SELECT ... LIMIT. También hay que contar el número total de resultados para luego poner los enlaces a las siguientes páginas. Ahora es cuando se muestran todos los resultados, y a continuación los enlaces al resto de páginas. En cada enlace le tienes que pasar como parámetro GET el número de página a mostrar para poder calcular los resultados que se muestren.
Como ves, es bastante sencillo de entender, no creo que tengas ningún problema, pero si lo tienes me lo comentas.