If you look in the MasterPage you will see that there is a DelegateControl called SmallSearchInputBox.
DelegateControls let you swap out controls for controls defined in features at a web/site/application/farm level. For more details see the linked blog post, it's Targetted at SP2007, but the concept is the same in 2010.
http://blogs.msdn.com/b/pavankumar/archive/2009/03/24/customizing-small-search-box.aspx
You can also copy this file into your own feature as a starting point.
<SharePointHive>\14\TEMPLATE\FEATURES\OSearchBasicFeature\SearchArea.xml
Simply change the two properties for "GoImageUrl" and "GoImageUrlActive" (and optionally the RTL versions of them)