I might add that most people screw up the next step; the quality (aka relevance) of the search results. It’s one thing to get a beautiful UI. Google though was never known for beauty, but rather accuracy with results. I’ve seen orgs invest a great deal in beautiful search UIs but have the investment fail because the results themselves (the core of the user experience) don’t make any sense to users. We all have the experience of getting angry at some websites search functionality that doesn’t “get us” so we give up on it.
(Shameless plug I wrote a book on this :-p)