Las canciones y los emblemas estatales ensalzan los tesoros naturales y culturales del estado que representan. La canción del estado de Nuevo México es «O Fair New Mexico», un himno descriptivo que fue escrito por Elizabeth Garrett, la hija de Polinari Gutierez, y su esposo Pat Garrett, el ex alguacil del condado de Lincoln. Pat Garrett es conocido en la historia de Estados Unidos como el hombre que disparó y mató al famoso forajido occidental Billy the Kid. Elizabeth Garrett, que publicó la canción y registró derechos de autor en 1915, cantó su composición ante la asamblea legislativa del estado de Nuevo México en 1917. Su interpretación fue tan buena que, el 4 de marzo de 1917, los miembros de la legislatura votaron unánimemente por la canción para convertirse en uno de los símbolos permanentes del estado de Nuevo México. El gobernador Washington E. Lindsey firmó el proyecto de ley a tal efecto.
Elizabeth Garrett, la autora de la canción estatal de Nuevo México, nació el 8 de octubre de 1917. La tercera hija de una familia de ocho hijos, Elizabeth perdió la vista poco después de nacer como resultado de una aplicación de vitriolo azul que, irónicamente, fue suficiente, aplicado para prevenir infecciones. Sus padres la ayudaron a sobrellevar su ceguera y a tener una infancia normal y activa y, cuando tenía seis años, la enviaron a estudiar a Austin en la Escuela Estatal para Ciegos de Texas. Dada su aptitud para la música, también recibió formación vocal y de piano en Chicago y Nueva York. Trabajó como profesora de música y como soprano talentosa, y se hizo conocida por sus representaciones teatrales.
Dos décadas después de que su canción fuera seleccionada como la canción estatal de Nuevo México, en 1937, la asamblea legislativa de Nuevo México aprobó el proyecto de ley Elizabeth Garrett. Este proyecto de ley, que recibió el apoyo generalizado de políticos y ciudadanos, le otorgó un pago mensual de por vida en agradecimiento por escribir la canción del estado de Nuevo México. Elizabeth murió en 1947, y el título de su canción más famosa, «O Fair New Mexico», está inscrito en su lápida.
Además de la canción estatal de Nuevo México, el estado ha tenido la «Marcha de Nuevo México» dedicada a ella por el famoso compositor John Philip Sousa en 1928. En 1971, la canción española «Así es Nuevo Mejico», que fue escrita por el compositor Amadeo Lucero, se presentó ante la legislatura del estado de Nuevo México y fue seleccionado como la canción estatal en español de Nuevo México.