Restyling the Search Widget?

I am trying to work out how to restyle the Search Widget - I can't find anything in the forums so far - probably because the word "search" appears on almost every page.

Anyway, I am trying to restyle the widget as follows:

Nothing exciting, but with a couple of styles it fits what the designer had in mind! Unfortunately I can't work out how to get this to call the search routine against my "All Content" index, not can I work out how to reskin the inbuilt Search Widget to look like this rather than a textbox and a standard button.

Any help would be greatly appreciated!

Thanks,
Paul