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)