Что наследуется в ООП?
Класс наследуется, интерфейс реализуется.interface I {}
class A {}
class B extends A implements I {}
Класс обычно называют чертежом объекта. А интерфейс - это контракт, который объект обязан выполнить.
Возьмем, например, Велосипед, Грузовик и Мотоцикл.Мотоцикл - это почти Велосипед, он делается по тому же чертежу с небольшими дополнениями. Это наследование. Грузовик при этом ни от Велосипеда, ни от Мотоцикла не наследуется, у него совсем другой чертёж.
Но каждый из этих объектов реализует контракт ТранспортноеСредство. Если у вас есть объект, являющийся ТранспортнымСредством, вы всегда уверены, что доедете из пункта А в пункт Б и при этом вам совершенно неважно сколько у этого объекта колёс.
А вот если у вас есть контракт Автомобиль, то вы знаете, что можете выполнить такие действия как ОткрытьКапот, ВключитьСтеклоочистители. Велосипед при этом не сможет реализовать такой интерфейс. А Грузовик будет реализовывать оба контракта: хотите - передвигайтесь, хотите - открывайте капот.
> Наследуется сам Класс или его Интерфейс?
Что значит "его интерфейс"?
Интерфейс - это отдельная архитектурная единица, такая же, как и класс. Описывается ключевым словом "interface". 
По умолчанию у класса нет никакого интерфейса (если он сам его не реализует).
---
Если класс наследует класс (в Java это extends), то наследуются его методы, поля, свойства. То есть дочерний класс приобретает все члены базового, и может еще добавить что-то от себя (или переопределить унаследованное). Методы наследуются вместе с их реализацией, т.е. для дочернего класса они будут работать так же, как и для базового.
К примеру, возьмем GUI: классы Button и Label наследуют базовый класс Control, при этом свойства Left, Top, Width, Height, унаследованные от Control, в обоих классах работают одинаково. При этом  реализация и заголовки этих методов прописаны только в Control.
Если класс реализует интерфейс (в Java это implements), то он получает от интерфейса заголовки методов, а реализовать их он должен сам, причем все. В интерфейсе реализаций методов нету, в этом его главное отличие от класса.int foo() // - это заголовок метода
{ 
// а здесь реализация (она же определение, тело...) метода (собственно код)
}