Loyalty is an important theme in this play. Mowbray (a.k.a. Norfolk) is one of the few characters who actually remains loyal to Richard, even when he's accused (rightly!) by Henry Bolingbroke of having played a role in Gloucester's murder. The faceoff in Act 1 is embarrassing for Richard, who seems to have asked Mowbray to do his dirty work. This is sort of an open secret at court, and Bolingbroke knows that even though he's technically accusing Mowbray, he's really accusing Richard of the murder. Still, Mowbray never betrays the king. How does Richard repay the guy for his loyalty? By coldly banishing him from the kingdom... forever.
Mowbray's banishment says more about Richard's character than anything else. His inability to recognize or reward real loyalty, and his tendency to favor people who kiss up to him, are largely responsible for his downfall. In contrast, at the end of the play, King Henry tries to reverse Mowbray's banishment (and even give the guy his former titles and land back), showing that even though he and Mowbray were enemies, he recognizes Mowbray's "good" qualities (4.1.4): namely, his loyalty. Unfortunately, Mowbray has died by then.
We learn from the Bishop of Carlisle that Mowbray spent his time in exile fighting in some holy wars before retiring to Venice, where he "gave / His body to that pleasant country's earth, / And his pure soul unto his captain, Christ" (4.1.1). Wow. By using the word "gave," Shakespeare even makes Mowbray's death sound like an act of generosity and loyalty, don't you think? He doesn't exactly sound like a murderer.