Q:

O que é programação genérica?

O que é programação genérica?
Trata-se de uma técnica ou um paradigma de programação?
Quando devemos usar esse conceito?

A:

Termo
Um paradigma é um estilo de programação, onde se aplica uma técnica. Então é uma técnica e pode ser um paradigma, conforme literatura especializada e reconhecida. Podemos dizer que é uma forma limitada do paradigma de metaprogramação.
A oficialização do paradigma ocorreu em 1989 pelo Musser e Stepanov (da STL), mas a técnica já era adotada pelo menos nos anos 70 (possivelmente até antes).
Pode-se falar que o termo é apenas uma forma de generalizar uma solução. Mas, desculpe o trocadilho (ah, desculpa nada, eu adorei fazê-lo :) ), esta é uma generalização do termo :P
Melhor contextualizado, genericidade é a capacidade de escrever códigos que atendem adequadamente mais de um tipo de dado. É uma forma de escrever um código onde o código tem um tipo coringa até que ele seja instanciado, aí o tipo real é colocado ali no lugar desse coringa.
Em linguagens tipadas alguns tipos já eram genéricos (paramétricos), especialmente array e ponteiro. A genericidade é a capacidade de criar seus próprios tipos de forma genérica.
Tecnicamente não precisa ser apenas tipos. Tem linguagem que aceita outras formas de parametrização. Você poderia, por exemplo, ter uma classe String<N> onde N é o tamanho do texto. Isso cria um novo tipo String com N caracteres de tamanho. Seria diferente de uma string comum que conhecemos com um tamanho definido internamente.
Falando em termos de SQL string normal é VARCHAR, essa que estou exemplificando é CHAR. Lembrando que VARCHAR só tem tamanho máximo (e olhe lá, não vou entrar em detalhes aqui), não tamanho definido, igual a string das linguagens. Em geral as pessoas jogam um CHAR(10) em string mesmo, mas não são tipos realmente equivalentes.
Algumas informações aqui serão baseadas nas implementações mais conhecidas, o paradigma não tem grandes exigências com a forma exata de funcionamento.
Que problema ele resolve
Em vez de escrever uma função que funcione bem para int e outra que faz exatamente a mesma coisa com float, porque não escrever um código só? Em linguagens dinâmicas isso é normal, o que vier ele "traça". Mas em linguagens de tipagem estática isso não é possível. Cada acesso à memória deve ser claramente baseado no tipo do dado. Isso traz algumas vantagens, que não vem ao caso aqui.
A desvantagem óbvia é obrigar duplicar esforços. A generecidade vem para resolver esse problema e fazer o código funcionar para vários tipos.
É muito comum que o compilador pegue uma função que tem um tipo genérico e replique ela por conta própria para cada tipo que for usado na aplicação.
Isso ajuda a performance, mas pode fazer o código ficar grande. Por isso nem sempre a solução é ideal (é na maioria). É bom porque não só reduz a repetição, mas torna o código mais DRY.
O mecanismo exato não é definido pelo paradigma, cada linguagem pode optar pelo jeito que achar melhor.
A principal vantagem é a segurança de tipos aproveitando o mesmo fonte. A segunda costuma ser a melhor performance por resolver certas coisas em tempo de compilação (a extensão disso varia muito em cada linguagem).
Função genérica
Exemplo em pseudocódigo:
T Soma<T>(T p1, T p2) { return p1 + p2; }
Soma(1, 2);
Soma(1.5, 2.7);

Funciona perfeitamente, no primeiro caso os parâmetros e retorno serão do tipo int e no segundo serão do tipo float. Por causa do uso da função haverá a criação de duas funções concretas no código alvo gerado pelo compilador:
int Soma(int p1, int p2) { return p1 + p2; }
float Soma(float p1, float p2) { return p1 + p2; }

É claro que qualquer tipo que for usado precisa ser capaz de fazer a adição de valores, se isso não for garantido, haverá problemas de compilação ou de execução. Mas depende de como cada linguagem trabalha, não vou entrar em detalhes agora.
Você pode pensar que é só frescura sintática, mas o tipo constante ali tem implicações na composição de memória e eventualmente na semântica do código (mesmo sendo sintaticamente o mesmo exceto pelo tipo).
A "super variável" que define o tipo (T no exemplo) pode ser usada em qualquer parte do código, dentro do escopo de sua definição, claro, onde caiba um tipo.
Classes genéricas
A ideia pode ser ampliada. É possível escrever uma classe com um parâmetro genérico onde precisar. Quando vê um List<int> é porque a definição da classe List foi escrita como List<T> e em todos os lugares que precisar do tipo que deve constar dentro desta lista, nesse exemplo, um int, o T será trocado por int. É quase uma substituição de texto no código fonte escrito. Claro que o compilador faz isto de forma robusta (é diferente de um pré processador que não entende bem o que está fazendo e pode dar problema).
var lista = new List<int>;
lista.Add(1); //ok
lista.Add("1"); // erro, ele não aceita string

Acho que nem preciso dizer que no fundo haverá uma classe nova para cada tipo que usar. Mas elas serão todas compatíveis e há algumas otimizações para economizar espaço.
Algumas linguagens otimizam mais que outras. C# é muito boa nisto, ela replica o que realmente precisa a reaproveita o que tem alinhamento de memória compatível (por causa de indireção). C++ não é, mas ela é mais flexível, tem um bom motivo para não ser, e tem técnica para evitar muita duplicação. A melhor é Java que não replica, mas tem várias desvantagens por causa disto, perdendo uma parte do motivo de usar genericidade (mas mantém o principal que é segurança de tipos). Não vou entrar em detalhes, não cabe aqui.
Pode-se pensar nesse T que vemos aí no código como uma super variável cujos valores possíveis são quaisquer tipos disponíveis. Só que essa variável fica disponível num nível mais acima e resolve na compilação.
Obviamente que se a aplicação só usar uma classe genérica com um tipo, só uma versão dela existirá. O mesmo vale para funções. O uso do item parametrizado (genérico) é que definirá quantas cópias existirão.
Esse é um recurso que pode, em algumas linguagens, ser usado para fazer o polimorfismo estático (paramétrico), que tem vantagens e desvantagens em relação ao polimorfismo dinâmico (de subtipo), mais tradicional, que usa virtualização de métodos. O polimorfismo ad hoc (estático ou dinâmico), conhecido como sobrecarga de função é outra coisa.
Lembra do problema da função que faz uma adição para qualquer tipo? É possível restringir os tipos que podem ser usados genericamente. Exemplo:
T Soma<T : Addable>(T p1, T p2) { return p1 + p2; }

Aqui o tipo tem que implementar a interface Addable para funcionar, ou seja, ele tem que ser capaz de fazer uma adição. Isso resolve o problema. Note que esse é um exemplo abstrato em uma linguagem fictícia. Desconheço alguma linguagem que tenha tal interface (tem algumas que tem algo parecido).
class MinhaClasse<T: Widget> {
    private T widget;
    set(T w) { widget = w; }
    T get() { return widget; }
}
var x = new MinhaClasse<Button>(); //Button é um Widget
x.set(new Button());
x.set(new TextEdit());  //TextEdit é um Widget
print(x.get()); //imprime algo do TextEdit
var y = new MinhaClasse<Stream>(); //não funciona porque não é um Widget

Isso evita ter que escrever (o que é exatamente o que o compilador fará por você):
class MinhaClasse {
    private Button widget;
    set(Button w) { widget = w; }
    Button get() { return widget; }
}
class MinhaClasse {
    private TextEdit widget;
    set(TextEdit w) { widget = w; }
    TextEdit get() { return widget; }
}

Coloquei no GitHub para referência futura.
É possível que a linguagem tenha otimizações ou permita técnicas que não precise duplicar essas classes. De fato o normal é adotar internamente o polimorfismo dinâmico para evitar a duplicidade.
Alternativas
A alternativa pra isto é o tipo dinâmico (aceita qualquer coisa por definição, através de um mecanismo da linguagem ou por técnica, como o void * do C por exemplo, ou usar Object como era feito em C# e Java no passado) o que acaba com a segurança de tipos.
Ou ter um sistema de macro substituição de textos que reescreve o código com o tipo quando necessário. Isso até poderia funcionar, mas feito da forma correta é essencialmente o uso da genericidade de forma simplificada, sem contexto, como o C faz. É pedir pra ter dor de cabeça até sintática.
Onde e quando usar?
Em linguagens que pregam a segurança de tipos deve usar o tempo todo. Não é possível obter essa funcionalidade sem escrever pencas de códigos repetitivos. Qualquer lugar que detectar que um código será repetido para atender mais de um tipo, a genericidade deve ser aplicada.
Críticas
Algumas pessoas dizem que o código alvo acaba ficando grande demais (por isso existem técnicas auxiliares, como o polimorfismo dinâmico), mas existem técnicas que isso não ocorre. E existem outras que o programador pode ajudar evitar (especialização e derivação, por exemplo).
Há quem diga que o código fica menos legível, mas isso é bem questionável. Talvez ligeiramente mais difícil, tem que pensar um pouco mais sobre o problema, mas me parece ser algo adequado.
Por fim, as mensagens de erro não são as melhores possíveis para ajudar o programador. Isso depende da implementação. É verdade que em muitos casos será pelo menos um pouco pior, mas depois de alguma evolução ocorrida é raro ter mensagens completamente sem sentido como ocorria no passado.
Perguntas relevantes com exemplos de uso:

Quando e por que devo utilizar classes templates Class <T> em Java?
Por que usar um retorno genérico?
Quais as diferenças entre Tipos Genéricos em C# e em Java?
Por que o polimorfismo não funciona com Genéricos?
Declaração de uma interface com where
O que é uma classe de tipo "class MinhaClasseExemplo<T> where T: new(){}"?
Tipo genérico em Java
O que é a restrição "class" em um tipo genérico?
Como obter atributo de um objeto de tipo genérico?
Como utilizar tipos genéricos com parâmetros de tipos?
Fazer um vetor genérico em Java
É possível retornar a classe filha através de um método na classe pai?
Qual a diferença entre "generics" (Java/C#) e "template" (C++)

