Seems like it should be relatively easy, but I'm having difficulties allowing anonymous users to enter a value in the search box without share point prompting that user for authentication. I have allowed anonymous users to access the site and that seems to be working fine. Any help would be appreciated
You might be interested to check this: http://blogs.objectsharp.com/post/2008/02/20/SharePoint-search-and-anonymous-users.aspx
Or on the other hand you can also create your own custom search page and redirect the users to this custom page. This will not cause the anonymous users a problem is searching content on SharePoint Site. But if you are using the default OSSSearchResults.aspx page then the above article should solve your problem.