Because of Terrence Malick's habit of cutting and editing his films repeatedly, much of the music that James Horner wrote for the film never made it to the final cut, except for a few fragments. In an interview, Horner said that Malick loved his score, but had no clue about what to do with it. He concluded that working with Malick was "the most disappointing experience I've ever had with a man" and that "I never felt so letdown by a filmmaker in my life".
Algonquin is a language spoken by natives in Canada that does indeed only have about 3000 speakers left today. The Algonquian language spoken in the movie, however, was a reconstruction of the East Algonquian language called Powhatan or Virginia Algonquian. There are no native speakers of this language alive today. The language went extinct at the end of the 18th century. Linguist and Professor for English at UNC Charlotte Blair A. Rudes reconstructed Virginia Algonquian based on other East Algonquian languages and John Smith's records (among others).
In an interview, Christian Bale spoke of the eccentric directing styles of Terrence Malick. He said that he wanted to see what Malick would do if he just walked out of a shot and towards the crew. Malick followed Christian with the camera and, as Christian put it, "[the crew] were running, and they were diving behind bushes to get away from the camera."
To elicit a more authentic performance, Terrence Malick forbade Colin Farrell and Q'orianka Kilcher from seeing each other prior to filming their first scene. They did accidentally run into each other prior to filming, Kilcher simply turned and walked away.
In preparation for the role, Colin Farrell read all seven of John Smith's books he published back in England on his accounts of The New World.