You may want to review the indexes on the tables used if the select is too slow. With proper indexes, even millions of records are returned in a few seconds.
Secondly, you may want to reduce the amount of data that is returned if that is to be displayed to the user. As you already said, a good paging mechanism will help you out.
Also, the SQL server caches the query plan and consecutive selects should be quite fast. If that is not happening, you should review query plans and see if there is something wrong. Actually do check the query plan as they suggest you about the missing indexes. Review the suggestions and if required implement them.
You are talking about some way to temporary persist the data somewhere. It is called Caching. There are lots of factor which determine your application caching mechanism for example - how much data is returned by the database, freshness of the data (frequent edits/updates), time for the data should be cached and so on.
For example if you have a very powerful web server (or a web farm) and considering the edits/updates on the data is not very high, I would get all the records at one go and keep them in the cache and select it from there. Reads from cache is lightning fast!
The topic is huge and takes a lot of time and research to excel.
I would say search Google for 'sql server indexes' and '.net caching' to start with.
Hope this gives you an idea.