For most of them I at least have a guess:

Costanoan--Costa Rica?
Nahuatl--Mexico?
Guarani--South America?
Quechua--Mexico or Central America?
Eskimo--yep
Carib--too easy, unless I have been deceived
Choctaw--um...midwest U.S.?
Arawak--no idea unless it's Alaska
Tupi--no idea
Algonquian--northeast U.S. and into Canada, although this actually came to be the
"umbrella name" under which several tribes united

Taino--no idea
Quechua--no idea but puts me in mind of Quebec
Aztec--Mexico
Aymara--no idea
Catawba--no idea
Maya--South America--Peru?
Salish--no idea
Araucanian--no idea
Miskito--no idea (I'm beginning to think I'm going to have
to retract my opening statement.)

Ojibwa--midwest/western U.S. ...I think
Chinook--way northern North America...west
Navajo--Mew Mexico area
Dakota--too easy
Hopi--next to the Navajos
Natick--no idea
Powhatan--augh, I should know this! Eastern U.S. ...?
Aleut--way northern North America
Cree--midwest U.S.
Nootka--no idea but sounds way northern
Narraganset--too easy
Pima--SW U.S.
Halkomelem--no idea
Munsee--never heard of this one or the one above
Massachuset--too easy
Muskogean--sort of northern-eastern midwest U.S.
Galibi--never heard of them, either
Micmac--Michigan?
Shawnee--northwestern midwest--came to be pretty fierce
********************************************************************************

At least was interesting (as opposed to the above):Could uh-uh and uh-unh come from Cherokee? They're Americanisms, and the former at least recalls the Cherokee negative, a nasalized high vowel. On the other hand, some have claimed an African origin for these expressions. And on the third hand-- you need a lot of hands in philology-- nasals with negatives and central vowels are suspiciously common across the world (like "mama" or "papa"), and are thus hard to attribute to borrowing.