Eu costumo dizer que: herança é um tipo de relação que estreita as possibilidades e implementação (interface) é um tipo de relação que expande as possibilidades.
Ah, não é apenas no java que isso é (ou deveria ser) priorizado. Basicamente, é em tudo o que você implementa o paradiga da orientação a objetos. A peculiaridade de não possuir suporte à herança múltipla, talvez, ajude para que este mito mantenha-se no java.
Bom, a herança visa evitar que você tenha duas ou mais classes com duplicidade de atributos e/ou métodos. Está ligada ao conceito de generalização da OO, apenas. Eventualmente, você pode trabalhar com polimorfismo.
Já a interface visa, primeiro, estabelecer um contrato entre o que você implementou e uma terceira parte, que pode ou não ser desenvolvido por ti, pelo time no qual você trabalha ou pela empresa onde isso ocorre.
Esse contrato, a interface, possui a declaração de métodos, sem corpo (ok, do java 8 para frente você já tem coisas como o default method). Todos os atributos inseridos numa interface será, automaticamente, static final, ou seja, são constantes (podendo ser, apenas, default ou public).
O objetivo de implementar uma interface está ligado a dois conceitos da OO: o primeiro (e mais óbvio): polimorfismo. Uma vez que a classe concreta que implementa uma interface é obrigada a dar corpo a cada método presente neste contrato, é a ideia fundamental de existir desses caras.
O segundo caso está ligado a encapsulamento em nível de classe. Com o uso de uma interface, você só expõe o que realmente precisa ser exposto.
Em geral, prefira composição/agtregação e implementação a herança.