Getting the total number of results and paginating are two different operations. For the sake of this example, let's assume that the query you're dealing with is

SELECT * FROM Orders WHERE OrderDate >= '1980-01-01' ORDER BY OrderDate

In this case, you would determine the total number of results using:

SELECT COUNT(*) FROM Orders WHERE OrderDate >= '1980-01-01'

...which may seem inefficient, but is actually pretty performant, assuming all indexes etc. are properly set up.

Next, to get actual results back in a paged fashion, the following query would be most efficient:

SELECT  *

FROM    ( SELECT    ROW_NUMBER() OVER ( ORDER BY OrderDate ) AS RowNum, *

          FROM      Orders

          WHERE     OrderDate >= '1980-01-01'

        ) AS RowConstrainedResult

WHERE   RowNum >= 1

    AND RowNum < 20

ORDER BY RowNum

This will return rows 1-19 of the original query. The cool thing here, especially for web apps, is that you don't have to keep any state, except the row numbers to be returned.