Já foi dito que a redundância é ter a mesma informação em dois lugares diferentes.
Para definir um pouco melhor o que é a mesma informação em dois lugares pegue um saldo e o movimento da conta, há informação redundante aí. Pelo movimento você tem o saldo. Esta redundância é ruim? Não. Dá mais performance assim e simplifica o acesso.
Pegue os dados do cliente de uma nota fiscal emitida. É o mesmo que está no cadastro de cliente. Isto é redundante, é ruim? Não, é fundamental porque se mudar os dados do cliente não pode mudar na nota fiscal emitida.
Tem uma série de situações que a redundância faz parte do modelo, até mesmo para dar mais robustez e confiabilidade, além das questões já citadas.
A redundância traz o problema que é preciso alguma coordenação para manter a consistência. Ela deve ser evitada quando não é necessária, por isso existe a normalização.
Coloquei no GitHub para referência futura.