This phenomenon is well attested. Objects of European craftsmanship in general were highly impressive to Native Americans during early contact, but the Bible was seen as a particular technological miracle or supernatural talisman, with some natives encountered by Protestant colonists in North Carolina "glad to touch it, to embrace it, to kisse it, to hold it to their brests and heades, and stroke over all their bodie with it."^1

The Jesuits in New France recorded the Algonquins' amazement with books and written messages, which were thought so highly of for the Jesuits to credibly threaten that "if they did any harm to [a Jesuit supply package] the little paper would accuse them."^2 Consider the solely oral means of history-keeping until that point. [EDIT: /u/demonicmonk is right in pointing out the wampum belt and other records, but these are still distinct from writing that captures particular words and language.] Writers/readers were seen as having spiritual powers to transmit knowledge without speaking, or even read the minds of others distant in time and space; the Bible was even more mystifying for preserving the words of the Black Robes' god, which had perhaps originally been lowered on a rope.

The Jesuits took advantage of this in their efforts to assume the social role of the shaman, and were glad to hand out Biblical quotations and hymns on paper, which were then used as ritual totems by illiterate Algonquins. On the other hand, the supernatural power of the written word was also blamed for epidemics and disasters. The Jesuits were accused of cursing particular people by writing down their names, or by opening certain malevolent books, which had to be destroyed. In general, the power of literacy served the Jesuits' goal of demonstrating the superiority of their religion, and came to be thought of as possessing broader supernatural powers. My source is Axtell's The Power of Print in the Eastern Woodlands.

1 David Beers Quinn, ed., The Roanoke Voyages, 1584-1590, 2 vols. (Hakluyt Society, London, 1955), 1, 375-377.

2 Gabriel Sagard-Théodat, Historie du Canada et voyages que les frères mineurs Recollects y ont faicts pour la conversion des infideles . . . (Paris, 1636), trans. H. H. Langton, MS 7, 285, University of Toronto Library.

Axtell, James. "The Power of Print in the Eastern Woodlands." The William and Mary Quarterly 44, no. 2 (1987), 300-09. 

In response to your second question, I'd recommend reading up on the development of the Cherokee Syllabary (eg the work of Ellen Cushman) and the incorporation of alphabetic text into wampum designs (eg the work of Daniel F. Harrison and Penelope Myrtle Kelsey). The scholarly literature on both of these topics addresses the nature of different Native American knowledge systems (in this case Cherokee and Iroquois, although wampum was used by most nations speaking Algonquin languages too) and how they responded to the introduction of European alphabetic texts. Further south, a LOT of work is being done right now on the khipus, the system of record-keeping that the Inca used in their vast empire and which had precedents as far back as the Wari Empire. Check out the work of Sabine Hyland and Gary Urton if you want to learn more about khipus; Hyland in particular is publishing a lot of material about how khipus encoded information, including the first phonetic decipherment of a khipu element, and how alphabetic and khipu texts interacted during the colonial period (eg the development of hybrid 'khipu boards').