best paging strategies for large datasets?

Hi,

I have a large dataset (page 1 at http://www.cruisefish.net/stat.md) and
am in the process of developping a pager to let users leaf through it
(30K rows).

Ideally I'd like to know when requesting any 'page' of data where I am
within the dataset: how many pages are available each way, etc.

Of course that can be done by doing a count(*) query before requesting a
limit/offset subset. But the main query is already quite slow, so I'd
like to minimize them.

But I am intrigued by window functions, especially the row_number() and
ntile(int) ones. 

Adding "row_number() over (order by <reverse query>)" to my query will
return the total number of rows in the first row, letting my deduce the
number of pages remaining, etc. row_number() apparently adds very little
cost to the main query.

And ntile(buckets) seems nice too but I need the total row count for it
to contain a 'page' number: ntile(row_count/page_size).

What better "paging" strategies are out there?

Thanks,