“I'm losing this Fight!”
Shamans are a people first appearing in the game Super Mario RPG: Legend of the Seven Stars, where they act as both NPC shopkeepers and enemies. They later made a re-appearance as non-enemy NPCs vital to the plot of all three of the Paper Mario series games. Their name comes from the word "shaman", meaning a learner magician (though Shamans in the series are shown to be capable of many magic).
The Shamans in Super Mario RPG: Legend of the Seven Stars are all identical, while those later introduced in the Paper Mario series have individual characteristics, as well hair, which they did not before.
 Super Mario RPG: Legend of the Seven Stars
Shamans are first encountered near The Sea area and the Sunken Ship as shopkeepers, selling Mario and his party items and weapons. After Mario buys items from the latter, the Shaman verifies whether Mario's password to access the ship's treasure room is correct or not, stating how many letters (if any at all) are correct and giving a hint on that the password relates to the sea.
They later appear in the Belome Temple, again, as merchants. One allows Mario access to a warp Trampoline for 100 coins, and another allows Mario to receive his fortune, as well as access to the rest of the temple, for 50 coins. There is another Shaman later on, who tells Mario that the fortune he receives from a Belome statue determines the destination of the next room. In the caverns of Land's End outside the temple, there is another Shaman, who sells Mario a Star for 800 coins.
 Paper Mario series
Merlon, Merlee, Merluvlee, Merlow, and Madam Merlar appearing in the Paper Mario series greatly resemble Shamans (in Super Paper Mario, Merlee and Merluvlee had different looks, and Merlow didn't appear in this game and the prequel). Wonky reveals in Paper Mario: The Thousand-Year Door that they may be a part of a sort of clan that names their members after their purposes, explaining their sporadic appearances in different lands. In Super Paper Mario, Nolrem, Merlight and Merloo resembled Shamans too.