COUNT & Pagination

I understand that COUNT queries are expensive. So I'm looking for advice on
displaying paginated query results.

I display my query results like this:

Displaying 1 to 50 of 2905.
1-50 | 51-100 | 101-150 | etc.

I do this by executing two queries. One is of the form:

SELECT <select list> FROM <view/table list> WHERE <filter> LIMIT m OFFSET n

The other is identical except that I replace the select list with COUNT(*).

I'm looking for suggestions to replace that COUNT query. I cannot use the
method of storing the number of records in a separate table because my queries
(a) involve joins, and (b) have a WHERE clause.

And an unrelated question:
I'm running PG 7.2.2 and want to upgrade to 7.4.1. I've never upgraded PG
before and I'm nervous. Can I simply run pg_dumpall, install 7.4.1, and then
feed the dump into psql? I'm planning to use pg_dumpall rather than pg_dump
because I want to preserve the users I've defined. My database is the only one
on the system.

Thanks.
-David (who would love to go to Bruce Momjian's boot camp)