Since you didn't mention a specific table name, here's something that you can play with... and it's very fast in the presence of the correct indexes... first page of a 1.2 million row table in <16 milliseconds... last page in less than half a second...
declare @start datetime
set @start = getdate()
--===== Declare the local variables
DECLARE @PageSize INT --How many rows to appear per page
DECLARE @PageNum INT --What page number to appear
DECLARE @Skip INT --Working variable for where to start for page
DECLARE @SQL VARCHAR(8000) --Holds dynamic SQL
--===== Set the local variables for pagesize and page
-- PageSize and PageNum would be parameters in a stored proc
SET @PageSize = 50
SET @PageNum = 4000
SET @Skip = @PageSize*@PageNum
--===== Create the dynamic SQL statement that will produce the page
SET @SQL =
'
SELECT c.*
FROM dbo.Customer c,
(
SELECT TOP '+STR(@PageSize)+ ' *
FROM dbo.Customer WITH (NOLOCK)
WHERE CustID NOT IN (SELECT TOP '+STR(@Skip)+' CustID
FROM dbo.Customer
ORDER BY CustID)
ORDER BY CustID
) d
WHERE c.CustID = d.CustID
'
--===== Produce the page
EXEC (@SQL)
print CONVERT(varchar(30),getdate()-@start,114)
--Jeff Moden