Kingdoms are the regions of Gems of War shown on the world map. Each kingdom has its own set of troops - for instance, Luther and Sheggra are from Broken Spire, the first kingdom players can access.
There are a number of activities that can be done in all kingdoms:
Quests are the main story or campaign arcs of the game. Each kingdom has its own quest line comprised of 20-30 battles to fight, ending with a final showdown with the kingdom's Legendary troop. Finishing a kingdom's quest line rewards the player with an Epic troop (the guiding character who has been with the player through the quests).
Challenges are an additional set of battles that are unlocked by reaching milestones in the quest line. Each kingdom has 7 challenges with 5 levels of difficulty. Completing challenges rewards the player with additional Souls, scaling with the difficulty of the challenges.
Explore mode is an unlimited battle area of a kingdom where the player is matched against a random team of troops largely (but not exclusively) from that kingdom. This mode has a vastly increased chance of getting higher-level Traitstones from battling here.
Kingdoms also pay tribute to the player, so it is wise to unlock more when possible.