I would focus on the McGaffey/Twin Springs area which has some excellent singletrack riding, ample camping opportunities and good access from Gallup. There is also a labyrinth of old logging roads that are fun to explore and fairly hard to get lost on.
This will take you to more info on that area (though not bikepacking specific):
http://www.galluptrails2010.com/gallup-area-trail-infoEven car camping at Hillso (QuakingAspen) or Twin Springs, riding the single track and exploring the logging roads by bike would be a great trip and a good intro to camping/biking.
I've explored the Zunis more to the southeast of that area - north of El Morro National Monument. This weekend I'm doing an overnighter south of there along the Chain of Crater Scenic Byway. The Continental Divide Trail passes through here and meanders among volcanic cinder cones.
Some images from a Zuni overnighter earlier this summer:
http://highaltitudehomestead.blogspot.com/