A number of sandstone areas can be found in western New Mexico, in the region near Gallup and Grants.
Of these, the sandstone sport climbing of Mentmore is perhaps best known. Mentmore is a popular stopover for those passing through this section of the state, and is popular among the few devoted local climbers who live in this region.
More adventurous climbing can be found in this area too. Church Rock near Gallup is a scenic sandstone spire.
Gallup is 2 hours west of Albuquerque on I-40; or East from Arizona it's about 2.5-3 hrs from Flag to Gallup.
A common question about climbing at Mentmore is: where do I stay?
One option is one of the numerous cheap hotels in Gallup (but be careful if you do this, there are some sketchy looking ones as well).
Some have also stayed right there at the crag. It's not the greatest environment but I have never heard of anyone being harassed. Don't be too surprised though, if someone comes in to illegally unload a pile of trash.
The best option for camping is, as written in one of the comments below, to stay in the McGaffee forest just east of Gallup. From Mentmore, get back onto I-40 and head east. Drive back through Gallup and then about 10 minutes east of Gallup take the McGaffee exit. Turn south and continue driving past Ft. Windgate. When you get into the forest there are plenty of roads to turn off onto that provide great primitive camping in a beautiful ponderosa forest.
If you just happened to bring a mountain bike, there is really great mountain biking in the forest as well.