(This is an expansion of a post I made to the extreme-programming mailing list last week, I guess it bears repeating since I can't be bothered writing anything new right now. It was a response to the comment: “I understand how implementation inheritance works in other languages... but so far I don't see if or why VB's lacking it is so bad... I'd like to hear comments on either side... anyone have any?”).
An object's interface (try to forget the way Java has co-opted the term for its own ends) is the set of messages to which it will respond. Thus, interface inheritance is the declaration that one class will respond to the same set of messages as another. This is the cornerstone of polymorphism: two objects that respond to a common set of messages (having a common interface) can be substitued for each other at compile- or run-time, allowing for more dynamic and flexible programming.
Interface inheritance is the most important aspect of inheritance Remember the advice from Design Patterns: “Program to an interface, not an implementation”. Without interface inheritance, a statically-typed language can not implement polymorphism, which would arguably make it not an object-oriented language.
Implementation inheritance, on the other hand, is a convenient shortcut. It's saying “because I'm inheriting the interface of my parent, it's most likely I want to behave in mostly the same way, so I'll respond the same way to these messages unless I'm specifically told otherwise.” Where we want to respond differently, we override the inherited method implementation with our own.
Implementation inheritance is convenient, but it comes with a number of important shortcomings that you have to keep in mind. It is far less flexible than pure interface inheritance, and it often ties you to the details of your superclass's implementation, breaking encapsulation.
A more general problem with inheritance that in most languages, (i.e. those without design-by-contract), an interface implies, but can not enforce a set of contracts that the class is expected to obey. If you inherit an interface, your class is expected to be able to polymorphically substitute for its superclass, so it needs to obey the same contracts as its superclass. A subclass should be a specialisation of the superclass, its behaviour a subset of the superclass's behaviour. If that is not true, you shouldn't be inheriting its interface.
This isn't helped by the mass of Teach Yourself Java books that encourage OO newcomers looking to implement some functionality, to look for a similar class and extend it. You can generally tell a programmer's OO experience by how well they avoid implementation inheritance, favouring instead encapsulation and programming to interfaces. (For a really bad misuse of inheritance in general, have a look at Java's Applet class, which in the name of convenience for newbies, breaks every tenet of good design by forcing the controller class to inherit an enormous part of the view.)
That said, implementation inheritance has its place. It's not essential for OO in the way implementation inheritance is, but it does save a lot of typing (and duplication) in common cases. Consider, for example, the Template Method pattern. (But then consider how you could replace any use of the Template Method pattern with a State or Strategy.)
In most OO languages, implementation and interface are closely intertwingled, and it's hard to explain the difference between the two to newcomers. Sometimes, I think that it was a mistake to join them as closely as has been done. Perhaps instead we should have broken them up completely and gone with class Foo implements Bar behaveslike Baz