Yep, that's pretty much what Val (who lives in Pecos) said.
I'm a NM lawyer who's been practicing criminal law for quite a while. Bear in mind that there are lots of places that you can't carry a gun, period (don't have time to list them all, but the list includes buses, schools, universities, prison grounds, jails, etc.).
That said, here's the statute that's relevant to your question.
NMSA 1978, § 30-7-2 (Unlawful carrying of a deadly weapon)
A. Unlawful carrying of a deadly weapon consists of carrying a concealed loaded firearm or any other type of deadly weapon anywhere, except in the following cases:
(1) in the person's residence or on real property belonging to him as owner, lessee, tenant or licensee;
(2) in a private automobile or other private means of conveyance, for lawful protection of the person's or another's person or property;
(3) by a peace officer in accordance with the policies of his law enforcement agency who is certified pursuant to the Law Enforcement Training Act [29-7-1 NMSA 1978];
(4) by a peace officer in accordance with the policies of his law enforcement agency who is employed on a temporary basis by that agency and who has successfully completed a course of firearms instruction prescribed by the New Mexico law enforcement academy or provided by a certified firearms instructor who is employed on a permanent basis by a law enforcement agency; or
(5) by a person in possession of a valid concealed handgun license issued to him by the department of public safety pursuant to the provisions of the Concealed Handgun Carry Act [29-19-1 NMSA 1978].
B. Nothing in this section shall be construed to prevent the carrying of any unloaded firearm.
C. Whoever commits unlawful carrying of a deadly weapon is guilty of a petty misdemeanor.
Please feel free to email me if you need clarification. There is no requirement in NM law that you hand over your CHL if stopped by police (see NMSA 1978, § 29-19-1, et seq.), but I would strongly advise that you do so.