Relevance for tweets / status updates is pretty simple: Newer = more relevant.
For example: http://www.google.com/search?q=san+francisco+halloween gives me a bunch of halloween stores
http://twitter.com/#search?q=san%20francisco%20halloween gives me a bunch of events (much more useful for me!)