Page fault é quando uma aplicação pede para acessar um endereço de memória e ele não está mapeado em RAM (é um pouco mais complexo que isto, mas vamos simplificar).
Memória virtual
Os sistemas operacionais modernos utilizam um sistema de memória virtual, então você tem até 4GB em 32 bits e teoricamente até 16EB em 64 bits (na prática costuma ser mais limitado). Você pode acessar tudo isso mesmo que não tenha RAM suficiente. Ele usa algum mecanismo para lidar com o excedente. Até onde eu sei todos jogam no armazenamento secundário (HDD, SSD, etc.) o que não está em uso.
O problema é que a aplicação não pode acessar diretamente algo fora da RAM. Então o sistema operacional precisa carregar o que está no secundário para o primário (RAM). Muito provavelmente colocando em cima de algo que estava em uso antes.
Para facilitar o trabalho isso é divido em páginas, geralmente de 4KB cada (existem páginas maiores, mas não vem ao caso). Então quando acessa um endereço na aplicação ele é um endereço falso, é virtual. Há uma tradução (o processador faz isso a pedido do sistema operacional, então praticamente não tem custo) desse endereço para o endereço físico real na memória. Por isso que mover dados pode custar bem barato já que ele só precisa mudar a tabela de páginas e não mexer na memória de fato, mais ou menos como ocorre com a tabela de arquivos em disco.
Por exemplo, um executável pode ser todo carregado para a memória ou não, depende do sistema operacional, de quanto tem memória livre. É comum só as páginas com código necessário ir carregando. Mas se tiver memória livre pode carregar tudo até para servir como cache. A carga pode não ser feita na hora da carga do executável até para otimizar a sua carga inicial. Depende de uma série de fatores.
Motivos para faltas de memória
Obviamente que se tentar acessar um endereço que está em uma página marcada como fora da RAM o sistema operacional terá que buscá-la no "disco", colocar na RAM e só aí deixar a aplicação acessar. Isso é o page fault. Falhou em acessar a memória diretamente. Obviamente que esse processo é absurdamente mais lento do que acessar a RAM diretamente.
A página pode estar indisponível naquele momento por alguma proteção específica.
A página tem um gatilho quando se tenta escrever nela e uma cópia precisa ser feita (copy on write).
A página está mapeada mas precisa ser tratada para uso. Para fazer alocações rápidas um mapeamento é feito apenas logicamente e só quando haverá uso efetivo é que ela será devidamente preparada.
Não entrei no mérito das faltas que são falhas e que não podem ser solucionadas pelo sistema operacional, como as proteções (semi)permanentes.
Consequências
Por isso é muito difícil gerenciar memória. Por isso que linguagens com GC podem não ser tão lentas no uso geral, elas ajudam evitar page faults. Por outro lado as coletas ajudam aumentar essas faltas. É um treco complicado de balancear.
Quanto menos page faults você tiver, mais rápido sua aplicação rodará. E não dá para controlar tanto assim. Em algumas linguagens é possível minimizar um pouco, pelo menos as faltas desnecessárias, mas dá um trabalhão e nada é garantido. Pra minimizar mais ainda bote muita RAM. E um SSD ajuda muito quando elas ocorrerem. Parece que com a NVRAM a armazenagem secundária chegará próximo da velocidade atual da RAM. Isso ajuda, mas ainda é melhor não ter faltas.
Adivinha o que acontece se tentar acessar algo que não deveria, algo que não pode ser mapeado? A aplicação quebra, o famoso General Protection Failure (GPF) ou alguma falha de proteção mais específica. Ou uma exceção é gerada para a aplicação tratar, se for possível. Sabe por que hoje quase não se vê mais GPF? Porque as pessoas usam linguagens que a tratam de forma diferente ou o programador aprendeu lidar com isso de uma forma mais bonitinha.
Muita gente acha que isso é chip de memória ruim, erro do sistema operacional, ou algo assim, mas é algo normal.
Ela é uma exceção em um nível interno do sistema operacional.
Abra o Task Manager ou um utilitário melhor como o Process Explorer e monitore as faltas. Abaixo uma lista de processos com suas faltas nesse momento. Tem dois processos que estão aumentando uns 4 ou 5 por segundo. Um deles é o FireFox. Por privacidade não copiei as colunas que podem identificar alguma coisa:
Quer aprender mais? O Windows mostra todo seu funcionamento em dois livros Windows Internals.
Coloquei no GitHub para referência futura.