Well, avoiding instance variables alone won't generally do the trick, since there's usually shared state involved somewhere (whether it's in the application context or in some global static fields). So the question about synchronization is justified. But as pointed out, the proper approach is not to synchronize methods, but to synchronize those code blocks that access the shared state (or to use locks, or any of the other facilities in java.util.concurrent).
If you're serious about concurrency -and in these days of multi-core CPUs, multi-CPU machines, and multi-request servers, which developer can afford not to be?- do yourself a favor and get one of the eminent books on the subject, either by Oaks/Wong or by Brian Goetz et al. Handling concurrency well without killing performance while making efficient use of Java's many features in this area is not easy to pick up otherwise.