hi!
i faced the same problem in my project.i followed the first method as you said- performing the search each time when moving to the next page or the required page number.i first thought of storing thr search results in session, but it became very difficult because we cannot predict the search because the data is huge.so to my knowledge better go for the first method i.e performing the search each time.
i think this suggestion may help you in solving the problem.
bye