Podrias hacerlo Asi:
if (!isset($pg))
$pg = 0; // $pg es la pagina actual
$cantidad=15; // cantidad de resultados por página
$cont = $pg * $cantidad;
$sql = mysql_query("SELECT * FROM contactos ORDER BY nombre LIMIT
$cont,$cantidad");
$contar = mysql_query("SELECT * FROM contactos ORDER BY nombre");
$total = mysql_num_rows($contar);
$pages = intval($total / $cantidad);
// Imprimir los resultados
while($array = mysql_fetch_array($sql)) {
imprimes los resultados de la consultas o lo que quieras.
// al final de todo creas los enlaces de paginación
echo "<p class=fonty >";
if ($pg != 0) {
$url = $pg - 1;
echo "<a href='$PHP_SELF?pg=".$url."'>« </a> ";
} else {
echo " ";
}
for ($i = 0; $i <= $pages; $i++) {
if ($i == $pg) {
if ($i == "0") {
echo "<b> 1 </b>";
} else {
$i = $i+1;
echo "<b> ".$i." </b>";
}
} else {
if ($i == "0") {
echo "<a href=$PHP_SELF?pg=".$i.">1</a> ";
} else {
echo "<a href='$PHP_SELF?pg=".$i."'>";
$i = $i+1;
echo $i."</a> ";
}
}
}
if ($pg < $pages) {
$url = $pg + 1;
echo "<a href='$PHP_SELF?pg=".$url."'> »</a>";
} else {
echo " ";
}
echo "</p>";
a mi me funciono perfecto