Eu tenho normalmente dificuldade em explicar o
que é a outras pessoas, por isso decidi escrever este artigo.

Variância neste contexto está diretamente relacionada com herança.
É relevante para compreender como é feito matching de parametros de
métodos, resultados de retorno, tipos genéricos e outros casos.

Existem três tipos de variância: invariância, covariância e contravariância.

• Covariância

Suponhamos o seguinte caso:

public class X {
    Object getValue() { return null; }
}

public class Y extends X {
    String getValue() { return null; }
}

A covariância neste caso está no tipo de retorno. Significa que se a
classe Y é mais específica que X (Y< X) então qualquer método de Y
que faça override a um método de X tem de retornar um tipo igual ou mais específico. Neste caso, o tipo de retorno do método que faz override é String, que é mais específico que Object.
Diz-se, pois, que os tipos de retornos em Java são covariantes (desde a versão 1.5).

Covariância

Contravariância é efectivamente o inverso de covariância. Significa
que se a classe Y é mais específica que X (Y<X) então qualquer
método de Y que faça override a um método de X tem de retornar um tipo igual ou mais genérico.

Em Java não há contravariância e overriding de métodos é sempre
invariante que passo a explicar de seguida. É no entanto possível ter
contravariância usando wildcards de generics.

Invariância

Em Java overriding de métodos é invariante, ou seja, para se
redefinir um método numa subclasse, os parâmetros têm de ser
exactamente do mesmo tipo do seu ancestror.

Este comportamento é muitas vezes descurado, veja-se o seguinte exemplo:

public class A {
    boolean equals(A object) {
        //Fantastico, sempre igual
        return true;
    }
}

Como o overriding é invariante, não estamos na realidade a fazer
override do método boolean equals(Object o) mas sim overload,
adicionando um novo método com outra assinatura. O pior é que passa
completamente despercebido.

A solução desde Java 5 é adicionar a anotação @Override que vai
permitir que o compilador detecte estes casos e informe que não estamos
realmente a redifinir um método. Aliás, todos os IDEs decentes sugerem
que se adicione esta anotação.

Uma nota sobre Generics

As noções de covariância e contravariância são importantes de ter
presente quando definindo classes tipificadas com generics,
especialmente quando se usam as wildcards para explicitamente definir
relações entre tipos. Não estamos a definir realmente relações
hierárquicas entre tipos, pois não há a relação de herança entre
classes genéricas mas estamos a definir relações entre os tipos que
parametrizam essa classe, se me consigo fazer entender.

Por exemplo:

public class Teste {
    void pseudoCovariante(List<? extends A> param) {}

    void pseudoContravariante(List<? super A> param) {}
}

Aqui definimos dois métodos para dar exemplos de como dotar classes
tipificadas de noções de contravariância e covariância, já que se não
usarmos wildcards temos parâmetros invariantes.

Espero ter conseguido explicar os conceitos básicos. Estas noções
aparecem em diversos textos sobre linguagens de programação e é
essencial compreende-las para se entender bem o sistema de
tipos da linguagem Java.