While you need to remember that thread safety has to take into account the surrounding code as well, you appear to be in luck. The fact that Matchers are created using the Pattern's matcher factory method and lack public constructors is a positive sign. Likewise, you use the compile static method to create the encompassing Pattern.
So, in short, if you do something like the example:
Pattern p = Pattern.compile("a*b");
Matcher m = p.matcher("aaaaab");
boolean b = m.matches();
you should be doing pretty well.
Follow-up to the code example for clarity: note that this example strongly implies that the Matcher thus created is thread-local with the Pattern and the test. I.e., you should not expose the Matcher thus created to any other threads.
Frankly, that's the risk of any thread-safety question. The reality is that any code can be made thread-unsafe if you try hard enough. Fortunately, there are wonderful books that teach us a whole bunch of ways that we could ruin our code. If we stay away from those mistakes, we greatly reduce our own probability of threading problems.
compile()
method might not be. There have been two or three bugs over the years that caused compilation to fail in multithreaded environments. I would recommend doing the compilation in a synchronized block. – Primp