PHP & MySQL Pagination

Use LIMIT.

SELECT *
FROM redirect
WHERE user_id = '35251' 
ORDER BY timestamp
LIMIT 40, 10

40 is how many records to skip, 10 is how many to display.

There are also a few problems with your PHP. You use backticks (not single quotes) to surround table and column names. And you shouldn't use string concatenation to build your query.

Here is a nice starting point:

<?php

// insert your mysql connection code here

$perPage = 10;
$page = (isset($_GET['page'])) ? (int)$_GET['page'] : 1;
$startAt = $perPage * ($page - 1);

$query = "SELECT COUNT(*) as total FROM redirect
WHERE user_id = '".$_SESSION['user_id']."'";
$r = mysql_fetch_assoc(mysql_query($query));

$totalPages = ceil($r['total'] / $perPage);

$links = "";
for ($i = 1; $i <= $totalPages; $i++) {
  $links .= ($i != $page ) 
            ? "<a href='index.php?page=$i'>Page $i</a> "
            : "$page ";
}


$r = mysql_query($query);

$query = "SELECT * FROM 'redirect'
WHERE 'user_id'= \''.$_SESSION['user_id'].' \' 
ORDER BY 'timestamp' LIMIT $startAt, $perPage";

$r = mysql_query($query);

// display results here the way you want

echo $links; // show links to other pages