The native version of the Medicine Man can be trained at a Trading Post built on a Maya settlement, until The Asian Dynasties. Since The Asian Dynasties, due to a bug, the option to train Native Medicine Men from Trading Posts built in a Maya settlement is missing, being possible to train them only from Native Embassies. They can also be rescued from treasures.
There is an unused portrait and textures for the Sioux Holy Dance button for the Sioux Medicine Man in The WarChiefs. This was corrected in the Definitive Edition, where the Lakota Healer uses its own portrait and specific textures for the Healers Ceremony button (since update 3552).
Both "Medicine Man" and "Shaman" refer to Native American healers and spiritual leaders. "Medicine Man" can be misleading, as not all were male and many of their responsibilities had little to do with physical healing. These Shaman were responsible for both the physical and the spiritual health of the people in their tribe.