The folks here are correct, that relaxation is the way to go.
However, as an instructor (Karate), I can tell you right away, that constantly telling someone to relax isn't going to solve the problem. Pointing out negatives and telling someone to do the opposite doesn't really appeal to the human mind very well, especially since it can be difficult to constantly force relaxation.
The easier way is to tense certain areas in the body where such tension is a good thing. This is something that you can constantly do, since you're not really focused on the relaxation part itself.
For example, you can focus on tensing your abs slightly. This action alone can help you relax the shoulders (where you don't want the tension), since you're focused on something that you can control 100% consciously, instead of trying to focus on something you can't control 100%.
Other things you can do is to give your armpits a gentle squeeze while sparring. This action helps tense the lats, which in turn, forces your shoulders to relax.