It's not Shlemiel's algorithm; getting page 16 takes pretty much exactly as long as getting page 1.
Yes, you do need a new query per page, but each of these queries gets only one page's worth of data. The alternatives are worse: If you get all data in one go and then filter it, you will still need one query per request, but now each of these queries gets the entire result set, and you'll be doing the partitioning in PHP - but a DBMS is much better at this than your hand-written PHP code. You could cache the whole thing, but this has two downsides: you still query the entire data set on first load, which means any request on a stale cache takes way longer than necessary, and you need to implement caching, which could add some significant overhead. Also, just like in the uncached example, you still need to do the pagination in PHP.
Should it turn out that your solution is too slow, you should first look at your database schema. Make sure you have the appropriate indexes on the relevant tables. Denormalize if you have to. If that doesn't cut it, consider caching individual pages.
And finally, if you need search functionality that scales, consider using something that specializes in indexing documents, e.g. Solr. These things are much better at indexing and searching documents than MySQL could ever hope to be.