Use static because there's no point in making a copy of these things in every instance of the class. I wouldn't go so far as to call it a performance issue as much as just being tidy and more correct in the semantic meaning.
Use final to make it clear to all readers (and the compiler) that you don't intend for these to ever change.
Using an interface depends. If this class is the primary or only consumer of the constants, I'd be happy to put them there. A "Constants" class for the whole system is not appealing. I'd try to keep them close to where you really use them.
Think about whether THREE should equal "2".
I assume that was a quick typo.
Another design that works well:
This is not an exact replacement for your Strings. You could compare your Strings against some user-entered String. But if you want people to call your method with one of several values you provide, this will do it. The type on the method argument tells them what they're dealing with where String does not.
[ August 07, 2007: Message edited by: Stan James ]