Everybody knows about Markov's work in this sense. The reason it worked so well was not just Google's application of Markov probability distributions, but their

Everybody knows about Markov's work in this sense. The reason it worked so well was not just Google's application of Markov probability distributions, but their integration with the then predominant search strategy of vector space models for page retrieval. The key insight Brin and Page had was to incorporate Markov's work as a scoring metric along with the results from a vector space search (it's all matrices anyways) and then generalize that to include other metrics to help weight pages to the top that are more likely to be what people are looking for. PageRank != Markov processes only, it's not even just Markov + Vector retrieval, if it was they'd be good to go and their staff of search quality engineers would be in the single digits. But Google has a large number of engineers who's sole purpose is to find ways of tweaking that basic weighting formula, using the user's query (and a handful of other metrics like custom search preferences, language, etc.) to float up good pages and sink down bad pages. I wouldn't be surprised if even Kleinberg's HITS hasn't made it into the formula in some way.