This is actually an easy change, no coding required.
It can be done directly from the control panel by going under Store Setup > Store Settings > Search tab and then selecting a different option for Default Product Sort, to be "Newest Items" like in this screenshot:
That's it. Your search order should now be changed for the entire store.