Crawling
Os mecanismos usam um sistema de crawling (informações detalhadas na Wikipedia). No fundo eles saem navegando como se fossem um usuário, só que é um robô, é um software que fica fazendo as requisições HTTP e armazenando o conteúdo achado em algum lugar.
Então tem basicamente duas formas de uma página entrar: uma é alguém manualmente colocar um endereço para ser buscado por esse pesquisador; a outra é ele avaliar um link encontrado em uma página HTML ou eventualmente algum outro tipo de recurso e usar esse endereço como base para iniciar outra busca.
Claro que é possível desenvolver técnicas para ter outras formas de descoberta, como analisar novos domínios registrados, por exemplo. Teria que ir muito na tentativa e erro do que poderia ter em algo novo. Duvido que seja uma técnica interessante. Curiosamente, em uma estratégia agressiva de concorrência, pode ser interessante pesquisar outro mecanismo de busca para ter uma referência :)
O tempo que demora para o conteúdo aparecer depende do que você deseja para seu buscador. Em tese é possível fazer isso praticamente real time, só que provavelmente haverá um desperdício de recursos. Esses mecanismos mais sofisticados devem ter uma forma para determinar se deve revisitar uma página com mais ou menos frequência baseado em estatísticas.
Além da política de revisita o robô costuma ter algumas políticas de seleção de conteúdo que interessa, que deve ser usado (respeitar a vontade do produtor do conteúdo de não indexar certas partes que são visíveis), e agressividade de requisições.
Parsing
Obviamente que o sistema precisa saber fazer um parsing de HTML, pelo menos para capturar os links e validá-los. Esta atividade pode ser usada para outras coisas úteis para o buscador.
Hoje é comum pesquisar além do HTML. Pesquisa-se PDF, TXT e outros tipos de documento, imagens e até chegam executar JavaScript.
Técnicas bem modernas e complexas de análise são necessárias para a forma como a web opera hoje em dia. Já é preciso fazer análise semântica do conteúdo para decidir o que fazer com ele.
Indexing
Com os dados coletados ele é armazenado em alguma forma que possa ser consultado. Em geral é feito uma indexação textual, ou inversa, como alguns gostam de chamar. Isso é semelhante ao que muitos bancos de dados possuem ou como ferramentas iguais ao Lucene funcionam.
Certamente será colocado em um banco de dados, mas provavelmente não um SQL. Será algum tipo de NoSQL, muito provavelmente feito para essa necessidade específica. Não é que o SQL não possa ser usado, mas ele não costuma ser o mais adequado.
Outro motivo para demorar para um conteúdo aparecer é esse banco de dados não ter que ficar sendo atualizado o tempo todo. Provavelmente há uma política de atualização dos índices, já que entra novas páginas o tempo todo e a reindexação pode ser custosa demais para ficar sendo realizada o tempo todo, então existe uma política de retardamento da atualização dos índices e fazer em lotes.
Searching
Aqui é a parte que dá acesso aos dados na forma que o usuário precisa.
A forma como ele achará, os critérios de relevância também dependem de como deseja trabalhar. É sabido que o Google coloca bastante peso na quantidade de links para aquela página.
Em geral a busca é distribuída. Costuma-se usar uma técnica de MapReduce (não confundir com as função de map()
e reduce()
que algumas bibliotecas possuem).
As buscas podem ficar em cache, o que pode atrasar um pouco a aparição de novos conteúdos, mas muito pouco e em casos bem específicos.
O conteúdo pode ser exposto de várias formas. As formas de filtrar e normalizar o conteúdo pode ser mais ou menos sofisticado. Por exemplo, na maior parte das vezes é mais fácil achar conteúdo na rede Stack Exchange pelo Google que na busca da SE. Mas há casos que a SE faz de forma mais especializada e acha melhor.
Conclusão
É possível usar ferramentas prontas para fazer estas tarefas, mas pelo volume não só será mais interessante fazer próprias mais adequadas, mas também deverá ter uma infraestrutura de distribuição da busca dos dados, indexação e acesso ao banco de dados para consumo. Se a indexação for bem mais restrita aí pode ser que compense algo pronto.
Como eu sei que o AP trabalha com .NET, existem ferramentas prontas para esta plataforma que fazem o grosso do trabalho (não o crawling, embora deve existir algo pronto menos conhecido, não é algo complicado). Os mais conhecidos usam o Solr. São o SolrNet e o SolrSharp. Tem para o Elastic Search também. (veja).
Parte do desafio é o trabalho de engenharia da busca em si (como ser relevante). Mas a maior parte do desafio é dar escala para tudo isto.
A Google ensina como funciona.
Técnicas que a Google usa.
Coloquei no GitHub para referência futura.