It comes from a tradition followed by some Native American tribes. At the end of a war, the tribes' chiefs would literally bury a hatchet as a symbolic gesture of their new peace.
Not all tribes followed this tradition. However, it likely predated the European settlement of the Americas, and it was seen as a solemn and important ceremony. One 1664 account describes the Iriquois proposing peace as “proclaim[ing] that they wish to unite all the nations of the earth and to hurl the hatchet so far into the depths of the earth that it shall never again be seen in the future.”
In fact, some sources claim that the practice of burying a hatchet came from the Iroquois. Per oral histories, the leaders Deganawidah and Hiawatha convinced the five tribes of the Iroquois Confederacy (the Mohawk, Cayuga, Oneida, Onondaga, and Seneca) to stop fighting, at which point they decided to bury their weapons under the roots of a white pine. The timing of this event is widely disputed, since the nature of oral traditions makes determining the exact date difficult, but it definitely happened prior to the mid-1600s.
According to etymology blog The Phrase Finder, one of the earliest uses of the exact phrase “bury the hatchet" comes from a 1747 book, The History of the Five Indian Nations of Canada. Here’s that passage:
The great Matter under Consideration with the Brethren is, how to strengthen themselves, and weaken their Enemy. My Opinion is, that the Brethren should fend Messengers to the Utawawas, Twibtwies, and the farther Indians, and to send back likewise some of the Prisoners of these Nations, if you have any left to bury the Hatchet, and to make a Covenant-chain, that they may put away all the French that are among them.
By the early 20th century, the practice was well known in the United States, and it was no longer exclusively associated with native tradition. In 1913, two former soldiers—one Confederate, one Union—commemorated the 50th anniversary of the Battle of Gettysburg by purchasing a hatchet from a local hardware store and burying it at the site of the battle.