According to a just released memo (PDF) from the U.S. government’s Office of Management and Budget, all publicly accessible federal government web sites and main entry points must have search capabilities by the end of 2005.
In some circumstances, mostly for small Web sites, agency officials may still rely on site maps or subject indexes, the memo states…some Internet experts also warn that building a better search engine is no panacea. “Search is, in many ways, second choice for most users,” said Larry Freed, chief executive officer of ForeSee Results, which sponsored portions of the ACSI poll. “Most users would rather navigate the system.”
More info in this Federal Computer Week article. You can read the full text of the OMB memo here (PDF). Section 5 deals with search.