I can point you in the write direction, if you need code examples, I'll have to come back tonight and try and get those for you.
Basically you need to first count the total records, sounds like you know how to do that already. You will need to do this each time the user changes pages, or make it persistent. This number will be used to build the result page links.
Basically:
$total_count = 1000; //where 1000 is the total results that can be displayed.
$page_count = $total_count % 60; //where 60 is the results per page.
So that gets you how many pages there are for the total results. We are half way there, we still need to pull the results for the specific page the user is viewing (we have to pull records 1-60, or 61-120 if they are on page 2, etc.)
To do this you want to use a little bit of SQL at the end of you query.
$x = 0; //where x is the starting record, in this case we are starting with the first record.
$y = 60; //where y is the number of records to pull, in this case 60.
$sql = "select * from table LIMIT $x, $y";
//again, the same thing but pulling results 60-120
$x = 60; //where x is the starting record, in this case we are starting with the first record.
$y = 60; //where y is the number of records to pull, in this case 60.
$sql = "select * from table LIMIT $x, $y";
That SQL is how you will pull the specific records for that page. You will need to use $page_count variable to build links, the links will have _GET vars that you will use as you xy for pulling records. That code will come something like.
$i = 1;
while($i <= $page_count){
$records_start = 60 *$i;
echo "<a href='script.php?x=1&y=60'>$i</a>
$i++;
}
Hope that helps!