Semplicemente dovrai usare la clausola LIMIT e costruirla dinamicamente in base alla pagina che si vuole caricare.

Questa problematica io di solito la affronto così:

uso 1 parametro che contiene il numero di record da visualizzare per pagina;
nella clausola LIMIT sai che dovrai indicare la prima cifra come il contatore del record da cui partire (base 0) , il numero di record da visualizzare (che sarà il nostro primo parametro)

la prima cifra la costruirai così

(numero_pagina-1)*record_per_pagina

Codice PHP:
<?php
$rowPerPage 
25;
$pageNumber = isset($_GET['p'])?$_GET['p']:1;
$con mysql_connect("localhost","peter","abc123");
if (!
$con)
  {
  die(
'Could not connect: ' mysql_error());
  }

mysql_select_db("my_db"$con);

$result mysql_query("SELECT * FROM Persons LIMIT ".($pageNumber-1)*$rowPerPage.",".$rowPerPage);

echo 
"<table border='1'>
<tr>
<th>Firstname</th>
<th>Lastname</th>
</tr>"
;

while(
$row mysql_fetch_array($result))
  {
  echo 
"<tr>";
  echo 
"<td>" $row['FirstName'] . "</td>";
  echo 
"<td>" $row['LastName'] . "</td>";
  echo 
"</tr>";
  }
echo 
"</table>";
if(
$pageNumber>1)
  echo 
"<a href=\"?p=".$pageNumber-1."\">&lt;</a>;

echo "
<a href=\"?p=".$pageNumber+1."\">&gt;</a>;

mysql_close(
$con);
?>