Focus on measuring search quality and methodology first. Be a scientist. Great search teams obsess about methodology. Treat everything you try as a hypothesis, not guaranteed to work. Create a feedback loop that improves the pace of experimentation.
Other than that, the solution space is just as wide open as regular programming. It's just in many ways more frustrating because nobody knows what they really want from search, they just "know it when they see it" and no two users really can agree on what a good result is! :)
This is a very, very insightful point. I would add: never expect a singular "perfect" algorithm, but rather build a framework that lets you blend (and evaluate/weight) the signals from various hacks, workarounds, heuristics, and "proper" algorithms.
