What were battles between Native American tribes like?

The_Alaskan's answer is about as good a description of a specific tribal warfare as I've seen, cheers on that.

The answer to your question absolutely depended on many factors, and varied greatly by region. On the high plains, warfare was fundamentally and forever changed by the acquisition of the horse. Tactics and skills honed for hundreds of years changed radically. So even for a single tribe there can be different styles of combat.

Among some Anishinaabe tribes such as the Menominee or Potawatomi, chiefs would convene to decide on the plan for a raid upon a neighboring tribe. They would send messengers to their surrounding camps requesting warriors to participate. On the night/dawn before a raid, the warriors would go to a pre-determined place (usually deep in a forest) on the general route towards the chosen enemy camp. There they would create an altar or lodge, and there perform ceremonies designed to give bravery, luck and skill to the men, and receive blessings from leaders. Often there would be a 'war bundle' or 'medicine bundle' involved; it would be a store of talismans designed to aid the warriors in battle. There are records of snakeskins being used to grant strength; special concoctions of roots and tubers which granted invulnerability to enemy weapons.

Once the ceremonies had been concluded, the raid would be launched. Sometimes the attack would be a straight-forward rush upon a still-sleeping camp, with war clubs and hatchets used for close-quarter combat. Sometimes bows and arrows were used, but there is scant evidence of these tibes attempting to run down fleeing enemies or kill them once scattered in such small, targeted raids.

Often these raids would have been smallish, and largely for the purpose of deciding territorial disputes. But they could also be larger, and more coordinated. One particular example of this took place on the Brule River in northern Wisconsin, in 1842. A band of Santee warriors had been attacking scattered summer camps of La Pointe Ojibwe along Lake Superior. A La Pointe chief led his men to try and waylay a large Santee party. Finding themselves outnumbered, the Ojibwes sent out a skirmishing party to engage the Santees, while the main force lay in wait in the underbrush beside the river. The skirmishers fell back, and enticed the Santees to cross the river in pursuit. Once the Santee party was struggling up the bank, the La Pointes closed in from both flanks and routed the Santees. William Whipple Warren (a Metis historian of the 1840s and 50s) gives some good accounts in his 'History of the Ojibwe People), there's a revised edition that came out a few years ago.

Without throwing too much of a blanket over things, the element of surprise as a virtue, and decoy/surprise attacks were a common thread among many different cultures and styles of war both prior to and after white contact. Small parties (often no more than a score) of warriors would engage an unsuspecting enemy in an attempt to enforce territorial hunting boundaries or capture horses or goods.

These tactics were also employed against white soldiers. A decoy approach was used on more than one occasion; the general ploy would be that a small party of warriors would approach the US positions, feign some distress (pretending panic at encountering the white men at all, horse injuring a leg, sickness, etc), in an effort to goad the Americans into a head-on attack. Once the bait was taken, the smaller party would race back to the main body of native warriors and the true attack would be launched. This was used with great and infamous effect in the Fetterman fight outside fort Phil Kearny in 1866. The Heart of Everything that Is takes a long look at this battle and the tactics Red Cloud and other Lakota leaders used in their wars against the U.S Army.

Some books that discuss to varying degrees the individual tactics of various tribes include Empire of the Summer Moon about the Comanches, The Middle Ground: Indians, Empires, and Republics in the Great Lakes Region, 1650-1815, Canada's First Nations: A history of founding peoples from earliest times, Chief Joseph and the Flight of the Nez Perce, Crazy Horse and Custer, The Fighting Cheyennes and Counting Coup and Cutting Horses