Against my better judgment, I am going to add my two cents here. I am a native of the Land of Enchantment, also known as "Well by God, it IS a state." New Mexican food is similar in most respects to the food from northern Mexico, particularly the Chihuahua and Sonora areas. One mistake many people make when they think about Mexican food is that Mexican food is the same throughout Mexico, but this is patently false. The various climates and relative distances from the ocean have the expected impact on the food of the various regions. And, New Mexico being closest--geographically and climate-wise-- to the northern Mexican deserts, New Mexican food is most similar to this type of Mexican food.
However, New Mexican food has also been greatly influenced by the Native Americans of the area, including the Navajo, Apache, and Hopi. Thus, meat, corn, tomatoes, potatoes, and chiles--all foods native to the region--figure heavily into New Mexican cooking, and some dishes which are common in New Mexico are virtually unknown outside of the state.
Often, New Mexican food is slathered in a chile sauce, and New Mexican chile sauces, unlike mole, are fairly simple. They are a little more than just "chopped up chiles", but the idea is that the chile is the primary ingredient, although ground beef is often added to the green chile sauce and the best red chile sauce I ever ate was in Reserve, NM and contained antelope meat. Chile sauce should NEVER be confused with chili, the meat and beans concoction typical of Tex Mex.
Green chiles do not only grow in New Mexico, but in the opinion of many, the best green chiles are the Big Jims grown in the area around Hatch, NM. Indeed, Hatch has a green chile festival every year, and many people who are New Mexico natives order either freeze-dried or frozen roasted chiles to be sent to wherever they live. Green chiles are grown and eaten elsewhere, and another name for the Big Jim type long green chiles is Anaheim because they are also grown in the area of Anaheim, CA. The chiles from Anaheim tend to be much milder and less flavorful, though.
Tamales, so far as I can tell, are native to Mexico, and there are native recipes for tamales from many different regions. The type that is most common in New Mexico is, again, the northern Mexico type, consisting of a fairly smooth masa in a corn husk with a red chile and pork filling, and steamed. Carne adobada is perhaps not native to Mexico, but it sure the hell is eaten, in different variations, in most places south of the border. Guacamole is also, so far as I can tell, Mexican and, thus, also authentic New Mexican. Cheese, on the other hand, along with the other ingredients Tujague mentions are gringo additions, and thus deprecated.
And flat enchiladas are indeed a New Mexican food, but you won`t usually be able to order them in a restaurant. They are typically New Mexican home cooking.
The essential ingredients in New Mexico cooking are:
corn tortillas
flour tortillas
meat, but which kind depends a bit on where you are; some of us favor wild meats like venison, while others prefer the traditional pork, and the health nuts like chicken; some dishes need beef
green chile, preferably Big Jim variety
tomatoes, which are native to this area
red chile, preferably from Chimayo, NM
masa, a kind of corn meal used in tamale making
onion and garlic
cilantro and cumin
pinto beans and black beans
chorizo, a kind of spicy pork sausage*
potatoes, which are also native to the Americas*
hominy, a kind of big corn*
oregano, of the Mexican variety
*Note: There is a difference between New Mexican home cooking and the food found in restaurants. Rice is not native to this area, so the dish called Spanish rice, while popular in restaurants, is not really a native dish. Potatoes, which are native, are fairly common in New Mexican (and Mexican) home cooking though. Similarly, plenty of New Mexican restaurants don`t serve anything with chorizo, but most of the New Mexican homes I have known and eaten in have served it frequently. Hominy is essential for the very typical New Mexican dish, of American Indian origin, known as pozole. Again, pozole is generally not found in restaurants, but it is a typical home food.