"Writing" is a tricky term. Indigenous groups in what's now the US had property records, laws, and symbolically represented stories that could be read by others. What they didn't have was a system of symbols that can fully encode human speech (and vice versa). The latter is the typical definition of "writing" and it's not required to have the former.

On an unrelated note, Gwynne's book is fine as a fantasy story, but it's very badly regarded from the perspective of narrative history. Hämäläinen's Comanche Empire is a much better book arguing a largely similar position. Don't take that as applying to later books by the same author, sadly.