ALL FIREARMS MUST REMAIN IN VEHICLES. New Mexico has a strong pre-emption law, enforced by their Supreme Court . . .
Rest areas, according to handgunlaw.com(pdf) are not prohibited areas.
Rest areas can be dangerous places for travelers, especially single women. In 1998, two local Arizona organizations, Grassroots and S.A.F.E., joined forces to protest the illegal signs at the Sacaton rest area near Tucson. Within a month, Arizona DPS employees were busy removing the prohibition from Arizona rest area signs. The bad signs at the Arizona rest stops had identical wording to the New Mexico signs in paragraph 2, where the prohibition on firearms outside of the vehicle is listed.
Arizona continues to correct the odd old/bad sign that is found in place.
Recently, Second Amendment activists fought the Alabama Department of Transportation, won the support of Governor Bentley, and had illegal “No Weapon” signs taken down from Alabama rest areas. The similarity of the signs makes me wonder if someone in New Mexico made a conscious decision to ban firearms in rest areas, or if they simply copied a design for rest area signs.