This is a mistake that many beginning web developers make. In fact, I have recently seen some outrageously paid Java consultants make the same mistake.

Users can -- and do -- open multiple browser windows when working with your site. A session ID stored in a cookie is global to all browser windows. This means that if a user has two windows open with different searches going in them, paging trough the results will not work. One search will overwrite the other.

The right way to cache results is to do it based on the actual search input. Previous posters discussed how to do it, so I'm just adding a why.

Of course you will probably need to find a new search method soon if you're using a SQL "LIKE" clause to implement it, but at least caching will make paging through results reasonably fast.