I feel your pain. I've done that (search for "Mazda", say), and I could paste you the code, but really it would do more harm than good (I was slightly traumatized just reviewing it -- WHAT WAS I THINKING??? hehe :)

You want to do as Masem says and use COUNT(*) (which is optimized in MySQL) to get the total number of rows. Divide those into groups depending on the scale of the results. I ended up doing this:

        for (my $i=100; $i <= 1000; $i += 100) {
            if ($num_matched <= $i) {
                $rows = $i / 10;
                last;
            }
        }
        unless ($rows) {
            for (my $i=2000; $i <= 10000; $i += 1000) {
                if ($num_matched <= $i) {
                    $rows = $i / 10;
                    last;
                }
            }
        }
        $rows = 1000 if $num_matched > 10000;
[download]

Basically I had to play with it to get the number of results per page to be reasonable (if there are 50 results, then you want 1-10, 11-20, etc.., but then if there are 500 results you might want 1-100, 101-200, etc..).

Then the other main part is maintaining the "state" of the search results. So, if they're on page 3, you have to know that corresponds to "LIMIT 21,30" in the SQL, say. If you look at the link above, there is a CGI param called "offset" for that.