Printing from a software package could be pretty pricey. The idea of using larger scale maps is probably the way to go. If you can get library or academic discards, so much the better.
If not http://store.usgs.gov has all the maps you might want. You can download pdf's of the maps for free, and then order the ones you need. You need to go to the above link, scroll down to the map locator, and then click on the map locator.
They generally carry the following scales:
1:24,000 7.5' x 7.5'
1:100,000 60' (longitude) x 30' (latitude)
1:250,000 1 degree (longitude) by 2 degrees (latitude)
I forget what the size of the paper is, but even on 1:250,000 it's going to take a lot of room to cover the whole state.
The larger maps often don't show trails.
In most areas 1:500,000 or 1:1,000,000 scale maps may be available.
I copied the following table from the USGS website. It shows all the map scales that they carry.
|Series||Scale||1 inch represents|
|Standard quadrangle size|
(latitude by longitude)
|Puerto Rico 7.5 minute||1:20,000||1,667 feet||200 meters||7.5 by 7.5 minute||71|
|7.5 minute||1:24,000||2,000 feet (exact)||240 meters||7.5 by 7.5 minute||49 to 70|
|7.5 minute||1:25,000||2,083 feet||250 meters||7.5 by 7.5 minute||49 to 70|
|7.5 by 15 minute||1:25,000||2,083 feet||250 meters||7.5 by 15 minute|| 98 to 140|
|USGS-DMA 15 minute||1:50,000||4,166 feet||500 meters||15 by 15 minute||197 to 282|
|15 minute*||1:62,500||1 mile||625 meters||15 by 15 minute||197 to 282|
|Alaska Maps||1:63,360||1 mile (exact)||633.6 meters||15 by 20 to 36 minute||207 to 281|
|County Maps||1:50,000||4,166 feet||500 meters||County area||Varies|
|County Maps||1:100,000||1.6 miles||1 kilometer||County area||Varies|
|30 by 60 minute||1:100,000||1.6 miles||1 kilometer||30 by 60 minute||1,568 to 2,240|
|30 minute*||1:125,000||2 miles||1.25 kilometers||30 by 30 minute||786 to 1,124|
|1 degree by 2 degrees or 3 degrees||1:250,000||4 miles||2.5 kilometers||1° by 2° or 3°||4,580 to 8,669|
|State Maps||1:500,000||8 miles||5 kilometers||State area||Varies|
|State Maps||1:1,000,000||16 miles||10 kilometers||State area||Varies|
|U.S. Sectional Maps||1:2,000,000||32 miles||20 kilometers||State groups||Varies|
|Antarctica Maps||1:250,000||4 miles||2.5 kilometers||1° by 3° to 15°||4,089 to 8,336|
|Antarctica Maps||1:500,000||8 miles||5 kilometers||2° by 7.5°||28,174 to 30,462|
* Abandoned map series, but still available for ordering as black-and-white photographic