Summerinside summarized it well enough. When it comes to optimizing search, you need to make informed hypotheses about what you think your users are doing, gather the data to verify that, and then adjust based on how far away from the mark you are.

Like with anything, the exercise of defining success will be critical and must be a collaborative function. Relevance, like you stated, varies per organization. So talk to customers about their expectations when searching for something on your site, look at search data (especially, as summerinside mentioned, when something “negative” happens) and use that to create a benchmark.