Scaling up
O escalonamento vertical é botar mais capacidade de memória (principal e/ou de massa) e processamento. Ou seja, é comprar um hardware mais poderoso para dar conta do recado.
Em alguns casos basta criar mais processos/threads que está fazendo o scaling up, desde que o hardware já suporte esse aumento. Há casos que separar o banco de dados em vários dispositivos de armazenamento já seja uma escala vertical, novamente é escalar na mesma máquina.
O investimento é basicamente em hardware. Comprando mais processador. memória e armazenamento já tem uma capacidade aumentada.
Em alguns casos é mais questão de fazer uma simples configuração para alcançar o que o hardware único já suporta.
Também pode ser otimizar a aplicação para que ela desempenhe melhor e atenda mais do que fazia antes.
Scaling out
O escalonamento horizontal é colocar mais computadores para dar conta do recado. Claro que eles adicionam mais capacidade de processamento e memória também, na soma total.
É muito mais complexo fazer um escalonamento horizontal tanto do ponto de vista de gerenciamento quanto do ponto de vista de programação, ainda que existam ferramentas para facilitar. Não é só colocar os computadores, eles precisam "se falar" de forma consistente e adequada. Na verdade isso é considerado o problemas mais difícil de resolver na computação.
Por incrível que pareça pode ser mais barato que o vertical, pelo menos no custo da aquisição da infraestrutura já que é possível adquirir hardware mais simples e mais comum que costuma ser mais barato pela escala de produção. Claro que o custo de gerenciamento e desenvolvimento pode mudar o custo total.
Fora os casos que o vertical não comportaria a necessidade, afinal essa estratégia tem um limite que em tese o horizontal não tem, o horizontal tem a vantagem de ser mais tolerante a falhas, ou pelo menos ser mais fácil ter a operação de volta em caso de alguma falha.
Diferenças
Qualquer banco de dados minimamente estruturado pode fazer os dois tipos de escalonamento. O vertical não precisa nenhuma propriedade específica a não ser no caso de separar dados em vários dispositivos de armazenamento ou permitir várias linhas de processamento, por isso não é simples fazer em certas modelagens. O horizontal precisa de mecanismos que permitam e, se possível, facilitem o escalonamento horizontal. Não importa se ele é do tipo não relacional ou não, se usa SQL ou não.
Desconheço outros tipos, nem sei se é possível ter. Existem variações dessas formas, principalmente no horizontal existem muitas estratégias e técnicas. Também pode fazer um escalonamento híbrido.
São raras as aplicações que precisam de escala horizontal. Pelo menos no sentido de escala mesmo. Pode ser útil fazê-lo pela confiabilidade maior de ter mais de um nó atendendo as requisições, mas não que precise de mais recursos. O grosso da necessidade vem de aplicações web de alta demanda ou processamentos muito específicos.
Pode não parecer a mesma coisa mas tem uma pergunta que está relacionada, mostrando que escalar qualquer coisa horizontalmente pode parecer a solução, mas nem sempre resolve ou compensa a dificuldade que é inerente dela.
Coloquei no GitHub para referência futura.