Quick search uses the relevance order as default, but advanced search has all necessary options as Peter explained.
We are using an advanced search engine/server and search module built on it, so it is really the best approach to use relevance order for quick search. Of course order of the result might not look very logical for short keywords, but the current setting - as design - puts the heavy load on the search engine instead forum database that is a big matter on large forums like MrExcel Message Board.
That being said It might be possible to apply a customization to include a date order option next to the quick search box. Therefore I am bookmarking this thread to examine possible options.