Wordorigins.org

The origin of the name Mexico is not quite certain, but it probably takes its name from Mexitel, one of the names of the Aztec war god, also known as Huitzilopochti. The -co suffix was used be the Aztecs to denote a place; so Mexico would be the place of Mexitel, a reference to his temple. The temple lent its name to the city, which in turn lent it to the surrounding territory.

New Mexico, obviously, takes its name from the region to its south. The name is a calque of the Spanish name for the region. The province of Nuevo México was formed by the Spanish in 1598. (Making Santa Fe, founded in 1607, the oldest capital city in the United States and tied with Jamestown as the second oldest European settlement in the United States; St. Augustine in Florida is the oldest.)

New Mexico was acquired by the United States as a result of the Mexican-American War of 1847-48, along with the territory that would become California, Arizona, Nevada, Utah, and parts of Colorado. It became a state in 1912.

(Sources: Oxford English Dictionary, 3rd Edition; Illustrated Dictionary of Place Names)