Heh, this is interesting. I recently had the opportunity to hear Tom Kyte (from asktom.oracle.com) talk about this. He demonstrated how Google completely guesses the number of results in a search (and also how it slows pretty badly after the first 5 or so pages). He said to never give an exact count, just make a guess using cardinality from v$sql_plan. Or if you're using Intermedia it can give you a guess. He also said never to give a link to a "Last Page" - just give the user an option to sort the query in a different way. I think this is because Oracle is usually tuned to quickly get "First Rows" rather than "All Rows".
Some information here (search on the page for "The application we are developing should use pagination to show the results" and read Tom's answer):