You can use another tag instead of input and apply FontAwesome the normal way.
instead of your input with type image you can use this:
<i class="icon-search icon-2x"></i>
quick CSS:
.icon-search {
    color:white;
    background-color:black;
}
Here is a quick fiddle:
DEMO
You can style it a little better and add event functionality,  to the i object, which you can do by using a <button type="submit"> object instead of i, or with javascript.
The button sollution would be something like this:
<button type="submit" class="icon-search icon-large"></button>
And the CSS:
.icon-search {
    height:32px;
    width:32px;
    border: none;
    cursor: pointer;
    color:white;
    background-color:black;
    position:relative;
}
here is my fiddle updated with the button instead of i:
DEMO
Update: Using FontAwesome on any tag
The problem with FontAwsome is that its stylesheet uses :before pseudo-elements to add the icons to an element - and pseudo elements don't work/are not allowed on input elements. This is why using FontAwesome the normal way will not work with input.
But there is a solution - you can use FontAwesome as a regular font like so:
CSS:
input[type="submit"] {
    font-family: FontAwesome;
}
HTML:
<input type="submit" class="search" value="" />
The glyphs can be passed as values of the value attribute. The ascii codes for the individual letters/icons can be found in the FontAwesome css file, you just need to change them into a HTML ascii number like \f002 to  and it should work.
Link to the FontAwesome ascii code (cheatsheet): fortawesome.github.io/Font-Awesome/cheatsheet
The size of the icons can be easily adjusted via font-size.
See the above example using an input element in a jsfidde:
Update: FontAwesome 5
With FontAwesome version 5 the CSS required for this solution has changed - the font family name has changed and the font weight must be specified:
input[type="submit"] {
    font-family: "Font Awesome 5 Free"; // for the open access version
    font-size: 1.3333333333333333em;
    font-weight: 900;
}
See @WillFastie 's comment with link to updated fiddle bellow. Thanks!