A search engine system assists users in refining their searches by suggesting previously-submitted search phrases to such users. The search phrases are selected to suggest based on collected data regarding search behaviors of search engine users. In one embodiment, candidate search phrases are scored and selected to suggest based at least in-part on (a) a frequency with which each search phrase has been submitted, and/or (b) an evaluation of the "usefulness" of each search phrase, as reflected by post-query-submission actions of users who submitted the search phrase.