this little question intrigued me just enough to look into it a bit further :)
I tried this:
<dnn:SEARCH runat="server" id="dnnSEARCH" Submit='<%# "<img border=""0"" src=""search.gif"" />" %>'/>
The <%# %> construct means databinding, and this is done automatically at some stage during the loading of the skin. Not sure why, but at least in my test, the correct path of the skin was automatically prepended to the image file name
Source output in IE looks like this:
<a id="dnn_dnnSEARCH_cmdSearch" class="SkinObject" href=" __doPostBack('dnn$dnnSEARCH$cmdSearch','')"><img border="0" src="/DotNetNuke/Portals/_default/Skins/dnn-blue/search.gif" /></a>
Let me know if this works for you too ;)
<edit>
you can even make this localizable like this:
<dnn:SEARCH runat="server" id="dnnSEARCH" Submit='<%# "<img border=""0"" src=""search."+System.Threading.Thread.Currentthread.CurrentUICulture.Name+".gif"" />" %>'/>
which will render like this (if the current locale is en-US):
<a id="dnn_dnnSEARCH_cmdSearch" class="SkinObject" href=" __doPostBack('dnn$dnnSEARCH$cmdSearch','')"><img border="0" src="/DotNetNuke/Portals/_default/Skins/dnn-blue/search.en-US.gif" /></a>
</edit>
<edit2> removed too many closing quotes rendering an extra quote in final html </edit2>