Google's Matt Cutts, depicted here in an April Fools style animated GIF, posted a video on how Google goes about evaluating new search algorithms.
I summarized the three basic steps at Search Engine Land including (1) quality raters metrics, (2) live test metrics and (3) search quality launch team final review. You can watch the full video or read my summary there to learn more.
The interesting part, to me at least, was when he talked about how more clicks on a specific search result set typically means higher quality results except when it comes to webspam. Results with spam typically see a higher click through rate.
So that does make figuring out some algorithm changes harder but Google is pretty good at, according to Matt, figuring out the spam from the good results and they weed those outliers out pretty fast.
Here is the video:
Forum discussion at Google+.