@Jagster beat me to it, but if you follow that guide you’ll end up with something like this in the head tab of a theme component:
<script type="text/discourse-plugin" version="0.8">
api.replaceIcon('search', 'link');
</script>
Obviously you won’t want the link icon in there, but you get the gist. 