When I type a new question in SO, it displays the list of similar questions almost instantly? I imagine there must be some kind of distance computation between the asked question and the questions in the database. How do they implement this? Does the algorithm scale when there are more questions?
You may want to read a "Collective Intelligence" book, like link text.
Lucene can be used, or more commonly something that builds on Lucene like Solr (link text)
Basically it's just matter of calculating approximate distance between questions, usually implemented by using vector spaces. A simplification is to think of each unique word from either query being a value; if query has it, value is 1.0, if not, 0.0. And then create ordered vector of values, calculate cartesian distance (both have the word, 0 distance in one dimension, only one has it, 1; sum differences, take Nth root etc). But after that, it's better to scale words in order of relevancy, usually using TF/IDF (or similar). That's close to what Lucene does.
With Lucene you could just index all old questions, use the question being asked as the query, and choose highest ranking entry or entries. That's simple, fast, and possibly good enough. But there are many many ways to improve this obviously; so using Solr is a logical next step.
See previous question, Algorithm to find similar text.
I don't know how they implemented it, but you could implement it by using lucene. They have a query feature called proximity and fuzzy search. Where you use ~ and a number to specify the "distance"
I guess SO would pass in the tags and the subject.