Well, a cheap hack could be to add it to the footer, I mean where is the immutable law of web design that dictates all search boxes should be at the top of the page?

Personally, it's the current content of HN that interests me first and foremost (the NEW in NEWS). Putting the searchbox in the footer would emphasise this and not break the site design.