Should we @Override an interface's method implementation?

You should use @Override whenever possible. It prevents simple mistakes from being made. Example:

class C {
    @Override
    public boolean equals(SomeClass obj){
        // code ...
    }
}

This doesn't compile because it doesn't properly override public boolean equals(Object obj).

The same will go for methods that implement an interface (1.6 and above only) or override a Super class's method.

I believe that javac behaviour has changed - with 1.5 it prohibited the annotation, with 1.6 it doesn't. The annotation provides an extra compile-time check, so if you're using 1.6 I'd go for it.

You should always annotate methods with @Override if it's available.

In JDK 5 this means overriding methods of superclasses, in JDK 6, and 7 it means overriding methods of superclasses, and implementing methods of interfaces. The reason, as mentioned previously, is it allows the compiler to catch errors where you think you are overriding (or implementing) a method, but are actually defining a new method (different signature).

The equals(Object) vs. equals(YourObject) example is a standard case in point, but the same argument can be made for interface implementations.

I'd imagine the reason it's not mandatory to annotate implementing methods of interfaces is that JDK 5 flagged this as a compile error. If JDK 6 made this annotation mandatory, it would break backwards compatibility.

I am not an Eclipse user, but in other IDEs (IntelliJ), the @Override annotation is only added when implementing interface methods if the project is set as a JDK 6+ project. I would imagine that Eclipse is similar.

However, I would have preferred to see a different annotation for this usage, maybe an @Implements annotation.

I would use it at every opportunity. See When do you use Java's @Override annotation and why?