Edit: I just notice you said 'Store Locator Plus'. These instructions are for 'Store Locator'. Using Firebug, you can find what images you need to replace and follow the same outline as below, though.
You can find the search button images in /wp-content/uploads/sl-uploads/images. You can create your own search button images in Photoshop (or other) and upload them to that same folder with the SAME names as the current button names. You'll need:
Once you get those replaced, you'll have a much better looking search form! It looks like the developer is going to be providing themes in the future, but I wouldn't count on that, as making new buttons is relatively easy.