One of the best books of maps for Oklahoma is John Wesley Morris, Charles R. Goins, and Edwin C. McReynolds, Historical Atlas of Oklahoma, 3rd ed. Norman, Oklahoma: University of Oklahoma Press, 1986. (Family History Library book 976.6 E3m 1986; 1965 edition on film 1000357 item 3.)
United States Census Bureau State and County Map. This map will allow you to zoom in on any state or county in the United States and read the names of all of the neighboring counties.
The Family History Library has several maps, including some of the Indian Territory.
Printable maps are also available from the National Atlas of the United States -- http://nationalatlas.gov/printable.html