Using the {exp:query} tag in the licensed version of ExpressionEngine, you can pull the most recent searches performed by your users. The snippet below pulls the last 3 searches that returned a result, and links to the relevant search results page:
<ul class="recentsearches">
{exp:query sql="SELECT * FROM exp_search WHERE total_results > 0
ORDER BY RAND() DESC LIMIT 3"}
<li><a href="{path=search/results}{search_id}">{keywords}</a></li>
{/exp:query}
</ul>