The code
interface A {
    void print();
}
class B {
    public static void main(String[] args) {
        A a = new A() {
            public void print() {
                System.out.println("Message");
            }
        };
    }
}
is a shorthand for
interface A {
    void print();
}
class B {
    public static void main(String[] args) {
        class B$1 extends java.lang.Object implements A {
            B$1() {
                super();
            }
            public void print() {
                System.out.println("Message");
            }
        }
        A a = new B$1();
    }
}
With just one exception: If class B$1 is declared explicitly, it is possible to extend from it using class C extends B$1. However, it is not possible to extend from an anonymous class B$1 (JLS §8.1.4), even though it is not final (JLS §8.1.1.2).
That is, anonymous classes are still classes. As all classes (except java.lang.Object itself), even these classes extend java.lang.Object, directly or indirectly. If an anonymous class is specified using an interface, it extends java.lang.Object and implements that interface. If an anonymous class is specified using a class, it extends that class. In case the constuctor has arguments, the arguments are forwarded to super().
You can even (although definitely not recommended at all) insert a A a2 = new B$1(); later in main(), if you like. But really, don't do that, I'm just mentioning it to show what's going on under the hood.
You can observe this yourself by putting your source code in a separate directory, say, into AB.java, compile it, and then
- look at the class files that were generated.
- Use javap -c B$1to see how the anonymous class was generated byjavac.