We should document clearly which classes are thread-safe under which circumstances; both in the User Guide (http://userguide.icu-project.org/design) and on each class.
For an example of such documentation, see the "Synchronization" section in the ICU4J DateFormat class doc.
In particular, in Java, we cannot use "const" declarations to suggest thread-safety, so we just have to document it. We should explain Freezable semantics where available. We should point out immutable classes where we have them.
We should try to point out where classes are surprisingly not thread-safe. For example, Collator.compare() uses and modifies preallocated member objects (for performance, avoiding new helper object construction for each string comparison).
As a follow-up (other ticket), we could work to make thread safety more consistent and predictable.