In all honesty, I have never even noticed that HN didn't have search. Coming from reddit, I'm used to googling with "site:" and I've always done that with HN as well. My point is that HN does not need search.
It's an awesome resource, there are plenty of comments that are literally gems when you're stuck on something or starting with some new tech and that's when search comes in really handy.
For instance, how to start with clojure: http://news.ycombinator.com/item?id=1033503
tell me how you'd ever find that without a search?
First, I'd stare at the Clojure webpage, and try some examples in the REPL. I'd feel like I'm not grokking idiomatic Clojure, so I'd try some Google searches, but find nothing compelling. I'd hit random Clojure links on Hacker News and Reddit for a few weeks, but give up and move to a language with a more active community.
A year later, I'd accidentally find it at the bottom of an unrelated post and yell "If only I had that a year ago!"
Having a search button would simply "officialise" the default mode of searching on searchyc and then coming back here to submit the story.