1690s, "priest of the Ural-Altaic peoples of northern Asia," probably via German Schamane, from Russian sha'man, from Tungus saman, which, according to OED is perhaps from Chinese sha men "Buddhist monk," from Prakrit samaya-, from Sanskrit sramana-s "Buddhist ascetic." Extended to "similar personages in other parts" (OED), especially native Americans. Related: Shamanic.
also pow-wow, 1620s, "priest, conjurer, sorcerer among the North American natives," from a southern New England Algonquian language (probably Narragansett) powwaw "shaman, medicine man, Indian priest," from a verb meaning "to use divination, to dream," from Proto-Algonquian *pawe:wa "he dreams, one who dreams."
The meaning "magical ceremony among North American Indians" is recorded from 1660s. The general sense of "council, conference, meeting," especially if convivial, is recorded by 1812. Verb sense of "to confer, discuss, hold a consultation, deliberate over events" is attested from 1780.
"Native North American shaman," by 1801, from adoption of the word medicine in native speech with a sense of "magical influence; something supposed to possess curative, supernatural, or mysterious power." The U.S.-Canadian boundary they called the Medicine Line (attested by 1880), because it conferred a kind of magic protection: punishment for crimes committed on one side of it could be avoided by crossing over to the other. Compare Middle English use of medicine in secondary senses of "moral, psychological, or social remedy; safeguard, defense."
Unless some understanding is arrived at between the American and Canadian Governments that offenders may be promptly and vigorously dealt with, I very much fear that killing and stealing will increase to such an extent that the country along the border will be scarcely habitable. When the Indians are made to understand that the mere fact of "hopping" across the line does not exempt them from punishment, there will be a much greater guarantee of their good behaviour. Now they call the boundary the "Medicine line," because no matter what they have done upon one side they feel perfectly secure after having arrived upon the other. [Report of Superintendent L.N.F. Crozier, Dec. 1880, in "North-West Mounted Police Force Commissioner's Report," 1880]
Hence also medicine bag "pouch containing some article supposed to possess curative or magical powers, worn on the person by native North American people" (1802).