Caching search results would be fairly easy to implement and therefore should be considered.

Only a simple visitor should be needed producing a string describing Query tree, for example:

LogicalAnd( ContentTypeId( EQ, 9 ), LogicalOr( Field( IN, 5 ), SectionId( 2 ) ) ) ...

This string could then be hashed to use as a cache key.

Caching might not make sense in every case (fulltext search), so a mechanism to control it on API level should also be considered.