The relationship between a class and an interface is the same between itself and it's parent class. But I'd go with the super class, because I don't think it'll do any good to your classes just inheriting the Object class.

And for the code that penagate mentioned, it doesn't matter. If it's shared write it in the super otherwise give it a name and make it abstract (Must be overridden in each and all sub classes)