It is possible and is done all the time on hotmail, gmail, google, etc. the trick is to put all the search parameters into your query string (i.e., the $_GET vars) and formulate an sql query that returns only the records that correspond to the current critieria.
justsomeone is right that if you are storing several thousand records in session then you will be chewing up your server's memory and resources really fast once you have even a moderate number of users.
consider this, it might help you get started.
suppose your dbase had some fields:
id - integer
name - varchar
address - varchar
.
.
.
$sort_field_name = "name"; // this could be any field name you like
$search_text = "joe";
$page_number = 35;
$records_per_page = 10;
$record_offset = $page_number * $records_per_page;
$sql = "SELECT * FROM database_table WHERE name LIKE '%$search_test%' ORDER BY $sort_field_name LIMIT $record_offset, $records_per_page";
$result = mysql_query($sql)
or die("sql failed:" . sql);
while($row = mysql_fetch_assoc($result)) {
print_r($row);
}