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

Yes. It is recommended practise by Joshua Bloch in Effective 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.

Actually, Joshua Bloch, in the final paragraph of page 178 in Effective Java (2nd Ed.), says that it's not essential for methods of concrete classes that override abstract methods to use the Override annotation because the compiler would give an error anyway. However, "it is not harmful to do so".

I'd recommend choosing a strategy and sticking with it consistently.