The oldest record book in the famed Comstock Mining District, in what is now Nevada, dates to June 1859 just after the first strikes of gold and silver in June 8. Page 78 of the text includes a property transaction involving James "Old Virginny" Finney, whose nickname referred to the state of his birth. His popularity inspired the naming of the largest of the Comstock communities as Virginia City.

Finney's name is indicated with a large "X" and the words "His Mark" indicating that Finney was illiterate to the degree that he could not even sign his name. This is evidence of illiteracy on the frontier, but the negative evidence is that this is the only indication I found in that record book of complete illiteracy. Other people making transactions in that year could at least sign their name. Of course, signing one's name can be a step below functional literacy, but this bit of evidence nevertheless points to the answer to your question.

Besides that, we need to understand the frontier newspapers were extremely popular. People read a great deal and they devoured the news. There were no doubt many who were illiterate (just as there are today), but literacy was widespread.

All that said, there are many frontiers and the term "Old West" spans a great deal of geography and time. Each place and period would likely have a subtly different answer.