The first thing you'll want to do, is to insure you're rotating the proper direction. Make sure you're rotating the valve in an anticlockwise direction.
Apply a liberal amount of penetrating oil; allowing it to soak in for a bit, then give it another try. This will help clean the threads, as well as providing a bit of lubrication. Giving the threads a good second blast of penetrating oil can often remove more dirt and corrosion, which can be just what's needed to get the valve turning.
Size can matter
Using a wrench with a longer handle; or a breaker bar, can often help loosen stuck valves. Just be careful, you may be able to exert enough force to actually snap the valve.
Tap and twist
Tapping the end of the wrench with a non-marring mallet, can also help loosen a stuck threaded joint. Again, too much force can cause collateral damage, so be careful. Place the wrench on the valve, and gently rap the end in the direction of rotation.
Make sure you have the water heater inspected for proper operation, before and after replacing the temperature and pressure relief valve. Once installed, test the new valve to insure proper operation.