I still think a "Search" link at the bottom of the front page (or a note in the FAQ) would be good, whether it points to searchyc.com, "google site:news.ycombinator.com", etc. People probably only need to be told how to search once, but searching for how to search is a catch-22.