Try stretching out a little before you start playing. You read my mind, Glissando. Every day, before the first time you play, do these:
1. Stretch your arms straight over your head and grab one hand with the other. Keep your body straight, and bend with your torso to the left and to the right. You should feel the stretch in your triceps and under your shoulders (in the armpit area). Do that until those muscles feel warm and loose.
2. Put your arms at your side and slowly pull your shoulders up toward your ears as far as you can. Sort of like a shrugging motion. Do that until the muscles feel warm.
3. Do the same as #2, but when you get your shoulders as high as they go, roll them backward in a semi-circular motion back to your starting/resting place. Again, repeat until you feel warmed up.
This shouldn't take more than a minute or two to do, and remember to breathe regularly while doing these stretches. You may also find that if you take regular breaks while practicing, it will help. I never practice for more than 20-30 minutes without getting up and walking around, going to the bathroom, getting something to drink, etc. for a few minutes.
Everybody has to try and find out what works for him/her.
I personally recommend AGAINST stretching, particularly BEFORE a practice session. Stretching does not warm up muscles. Stretching requires muscles to be warmed up already. Stretching does not loosen muscles - it makes them tense. Instead, warm up your muscles by first lightly doing the activity that you will be doing more intensely later. Then you may stretch. Watch how athletes get going. They do it the same way.
If you get tense muscles, there is something wrong, namely the technique (barring an injury-type event). It does not have to be your piano-playing technique. If it's only your right shoulder, is it possible that you use you right arm throughout your day more often than your left arm? Do you work behind a computer all day long? All activities throughout the day require the correct technique, from opening doors to pushing buttons. Any of that could be the cause of your problems. Piano-playing may aggravate them or bring them out.
So, instead of stretching, I'd recommend pretty much the opposite, namely relaxation. Take a few minutes to relax completely (this takes months to learn...) to remove tension as much as possible. Then learn to avoid tension in the first place (this takes years...).
Start with paying more attention to find out if something gets tense. This alone will help you getting rid of a lot of tension throughout the day. Then learn to relax and, most importantly, to change the movements that have caused the tension in the first place.
Concerning your shoulder problems, keep in mind that when your shoulder muscles are tense, it means you are doing something wrong with your arms, not so much with your shoulders. If you'd be doing something wrong with your shoulders, then the muscles that control shoulder movements would get tense. Those are in the back.