When considering eye-tracking and the cognitive processes of identifying what an interface element is for, is it better for the button that activates the (often unlabelled) search operation to be on the left or the right of the search field?
I think the previous answers are correct in pointing out that for left to right reading languages the familiar UI pattern is to provide the search button on the right to continue with eye tracking that will follow the search text to the search button.
To complete this discussion, let's consider mobile UI patterns which offer consistency because of the keyboard. The search button acts similar to the "return" or "enter" button on a desktop, which is to the right. Also, note that each search field is preceded by a search icon to identify the input field regardless of a placeholder. These screenshots are from iOS6, iOS7, and android and shows this pattern is device agnostic.
One thing to consider is the "cancel" button. Although not apparent in these shots, the positioning is not consistent across apps. Some place it to the left, likely to signify going backwards, and others keep it to the right to remain in line with tracking.
I think for people whose language reads left to right will also interact with elements on a website in a similar fashion, plus as gurvinder points out, this has become the norm and is now what the vast majority of people will expect from a search bar or any kind of input which requires an action after.
If the search rewrites requires a button, then the button should be after the query input control, enabling a flow forward and also enabling use of the tab button to proceed forwards in the search flow.
(The tab button is useful when you have a lot of input to fill in and don't want to keep switching between keyboard and mouse.)
Update: Search button should be on the right side of the input box (Didn't explicitly mentioned it in the original answer).
Yes, simply because that is how it has always been and this is what people has been used to.
Unless, the button is auto-suggest (like google search) where upon selection of the suggested items search is suppose to trigger by itself. But there also, an explicit search button is required for more conservative users.
You may want to assess the default width of the search text entry area as well. This could expand on click but be a little smaller by default so that at a standard distance, the field and button can be seen in the field of view at the same time with less eye movement. Eye movement is really fast, but really you are creating a "word" element where the user can quickly identify the object as a whole (field + action button) and only have to do a quick recognition rather than have to read and interpret more deeply.
As it is written up, search button is now replace by enter keyboard action.
A specific search button is not mandatory at right in mono criteria search. But it is in multi criteria search.
In this case the right place is free for cancel cross icon and so the magify search icon is naturally place at the opposite of the cancel cross ah left.
This pattern also is used in url area of lots of internet browsers which naturally calls internet search engines when the user doesn't tape an URL web site but he tapes one or more words as it is a search field.
Don't forget writting the "search" word within the input area if you dont display thé search button.