On an aspx page, a user can enter some search criteria and get the data from
a database. The search results are stored in a dataset and then cached in a
Session (for datagrid paging). If the user opens a new browser window and
enters the new search criteria, then the new search results overwrite the
previous results in the Session. Now the datagrid on the first page will
display the search results from the second page.

How can I cache data independently (that is without overwriting each other)
on these pages?

Thanks.

You're actualy talking about caching for different instances of a page.
That's an issue you should solve by design.
You have many different ways you must consider according to the nature of
your application.

Normaly the place to hold a page instance specicifc data should be the view
state. If you'll save that in the view state there won't be any chance that
the data will be overriden in another instance.
One reason not to do that would be large size of data and small bandwith.
You can solve that by compressing the view state for example.
Though, if the data is too large for view state it might be too large for
the session as well.
What you should consider then is using paging through the SQL server
instead.