Basically, what you want to do is take all the code in search_box.tpl, copy and paste it into the section mentioned in header.tpl, then delete everything in search_box.tpl, at least that's what I did for version 2.4. May not work with other versions, but worth a try. REMEMBER TO RENAME YOUR ORIGINAL FILES SO YOU CAN REVERT BACK IF THIS SHOULD FAIL.