Ask HN: Advice on evaluating perceived search engine effectiveness

Many sites these days have a big emphasis on their internal search engines, which often use some sort of fuzzy ontology-based semantic matching.

Often the search engines are so complex, it is hard to judge how effective they are perceived by users. For example, how do you know if tweaking the weighting of a certain thing has actually improved the perceived search effectiveness or not?

I'm tempted to set up a simple user feedback tool that allows users to rate the search effectiveness if they want to (e.g. click a discrete "feedback" button somewhere, rate search effectiveness in one question, click submit, done). This at least will give me an understanding if a change to the search engine causes an improvement or not for certain query types.

However, I don't think this alone is the solution.I'm sure some of you HNers have faced this exact problem. Any advice?