Only a very few states require a permit to carry. For instance, in Nevada, the open carry of a firearm is not illegal. That means that no matter how often or diligently you search the Nevada Statutes, you will not find a statute stating that you can OC, nor a definition as to what it looks like.
I think at least one state defines 'holster' as something 'concealing whole or in part,' basically making it require a cc permit to do what most would consider oc.
If you haven't yet, check the "opencarry.org" maps:
http://www.opencarry.org/nm.html
It has a link to the nm statutes
http://www.conwaygreene.com/nmsu/lpext.dll?f=templates&fn=main-h.htm&2.0
While it isn't likely that 'open carry' will be defined, you might find some information by looking in the Conceal statutes; specifically, the defining terms in a statute that makes concealing a weapon a crime. Don't do what the definition is, and you should be
not-concealing.
JMHO, IANAL, and I didn't stay at a Holiday Inn Express last night (though there IS one just a few miles away from my home).