I have been exposed to some different Native American mythologies and there seem to be many differences. Are there any beliefs or stories that they all share?
The idea of the Coyote Trickster god is pretty widespread. My copy of The Book of the Navajo contains "The Tale of Coyote, the Troublemaker".
The Coyote is also known to the Apache in the "Badger carries Darkness: Coyote and Bobcat scratch each other"
A Cheyenne tale called "How he got tongue"
And a Blackfoot Coyote tale called "Little Friend Coyote"
A list of other tribes and legends can be found here