Lots of good advice.
Practice breath awareness. When you're sitting quietly, or when you're walking, actually follow your breath, say to yourself "In" and "Out" accordingly. Alternatively, particularly when quiet, become aware of your breath, and count breaths. Try to count ten breaths without losing concentration, it's surprisingly hard when you first start. These are actually meditation exercises, but can help your issue as well.
I would also begin with your kata, this is where you can learn proper coordination of breath with your movements. Every move (block/strike) can have an outward breath, every chambering can have an inward breath. (Roughly, since there are kata that are meant to be done in half-breaths, etc. as well). Talk more with your instructor about proper breathing in your kata, and focus on it. Slow down the movements if you have to.
When doing basic technique drills, you should be practicing breathing in a similar fashion. If your style does a "kia", then that should be a big clue as to when you breath out. Be sure to breath in before that :wink2:
Also, depending on your style (talk to your instructor), make sure you are breathing properly (as in where you are taking your breath).