I hardly think this guy needs any introduction. I started officially playing the game within the past year - well after Gamling's release. From my understanding he was a Rohan game-changer. Its hard to imagine a Rohan deck without him. That's how essential he is. I love to build Rohan decks and every time I build with Théoden Gamling has been there saving the day. In my opinion, he has reached "auto-include" status is nearly every Rohan build.
When you do not have any intention of discarding Rohan allies he still boasts a decent 2 and 2 HP. Considering is ability this is not bad for an ally who is saving other discarded allies. Théoden knocks off one resource to his cost allowing Gamling to enter the battle rather quickly. He can be a backup quester when you need it, or if you intend on ensuring Éomund will ready him later. Otherwise, you're likely going to find yourself using him purely for his ability, or taking your chances blocking a weaker enemy.
He adds special value with the Messenger of the King contract as well allowing you to pump out Rohan allies with Théoden, discard them through the card effect (or Ride to Ruin/Helm! Helm!), then save and repeat next round. You can't save them all, but you can sure as heck slap Unexpected Courage on him (for MoTK) and save two. He will also save you up to 2 card slots in a deck this way.