I published an FAQ some years ago which granted was a bit immature at the time but I still use the principal today in a more devloped and mature way. It could certainly be refined to make use of some of the advances in SQL server etc.
The approach basically uses a mix of the database and DAL / BLL layers to process the paging set.
In the first instance it hits the database to return list of all the primary keys for the result set. This is a prety small and efficient dataset if you use int as your primary key and a hash table or similar.
The DAL/BLL layer then processes this pulling out the total number of records and the current page we want. It then pulls the required page records using the primary keys which is very efficient.
To make this even more efficient I cache the initial list of primary keys so when the user requests the next page, etc all I have to do is look for the relevant primary keys in the cached list and pull the records I want based on primary key. This means the orginal complex query is only fired once regardless of the number of pages and any future requests on the same dataset only pull records based on known primary keys.