Should I add an @Override annotation when implementing abstract methods in Java?

I tend to prefer the use of @Override in this case, so that the method gets flagged in the subclasses if the superclass changes (either removing the method altogether, or changing its signature, etc.).

The only real difference is that without the annotation, if the method in the superclass/interface is changed or removed, the implementation in question simply becomes a "normal" method of that class. Thus you should add the annotation if you're implementing the method solely to fulfil the contract; and you probably shouldn't add it if the method makes sense in your class regardless of any implemented interfaces or inherited abstract methods.

Yes - again, it tells the compiler, "I really want to be overriding a method here. If there isn't a corresponding method to override, I've made a mistake and want to be told about it!"

Personally I think it's a pity that this is just an annotation rather than part of the language (as it is in C#) but that's the benefit of hindsight, of course.

Yes. It is recommended practise by Joshua Bloch in Effective Java.