The OpenSearch Suggestions Extension provides an interface for browser to suggest search terms. The obvious thing to do would be to suggest the most popular links via flex matching, preferring exact prefix matches.
This extension is supported by Firefox and Chrome. I’m not sure about Safari.
Related to #21.