Here is a small patch that adds a new template for the search form. 

http://jameswestby.net/scratch/search_template.diff

I wanted this so I could add a label to it easily.

I don't really think there's a problem with doing it except that it makes it
more easy to break the search box.