Info on hiking trails are somewhat difficult to obtain. You would most likely find more/better trail info in a third party overlay (transparent) mapset than in a 'full' topo mapset - but for any area you could get lucky.
I would first download the UT topo by IndyJpr listed here, with the direct:
http://www.miscjunk.org/mj/mp_uttopo.html The mapauthor used info from UT DOT which is very detailed, at least for the 4-wheel roads/trails around Moab. It is free, so you have nothing to loose but some time in downloading.
The entire state, and other mapsets can be installed to and viewed in MapSource on your computer. With only 24Mb on the GPSr, you will only be able to select and load to your GPSr a portion of UT. You can easily change which areas you have loaded to your GPSr.