The Eastern Woodlands--the area I study--has very little, if any, conclusive Pre-columbian interaction with Mesoamerica (only one artifact has been found in the region that is definitively Mesoamerican in origins). So I'm going to have to step a bit outside my comfort zone to help you with this question.

As /u/mullinbk said, the Southwest has an extensive Pre-columbian history of trade with Mesoamerica. Much of the Turquoise used for beads and artwork in the Valley of Mexico was originally mined in northwest Mexico and the American Southwest. The Ancestral Pueblo / "Anasazi" communities of Chaco Canyon, for example, flourished during the 10th Century, in part, because of the turquoise trade flowing out of the canyon to Mesoamerican markets in the south.

Immediately south of the Ancestral Pueblo region were the Mogollon (map, and among their major settlements was Paquimé, which I always like to point out because it's easy to see the connections between the Southwest cultures and Mesoamerican cultures. Technically speaking, Paquimé is just south of the modern US-Mexico border, but the Mogollon stretched both north and south of the modern borders. At Paquimé, the architecture is predominantly that of the Southwest, with its stone and adobe apartments, but it also has Mesoamerican features like I-shaped ballcourts (you can see one of them just left of center in this image of the ruins). Within the ruins, there are spaces dedicated to breeding parrots brought up from Mesoamerica, and the feathers of these southern birds were highly prized throughout the Southwest. Paquimé was founded in the 11th Century and would continue to be a major player in Southwest-Mesoamerican trade route until about 1450.

You'd probably also be interested in this section of the FAQs: Pre-Columbian Trade and Contact

Just wanted to point out that "Native American" refers to all natives from both North and South America- not only those from present day US.

Yes, a major trade center that connected the Pueblo people to contemporary Mexico is Casas Grandes, in Chihuahua, Mexico. The lower walls of the 2,000-room adobe structure still stand. It included workshops and storage rooms. Its construction is thought to have begun in 700 CE and continued to its height in the 14th and 15th centuries.

Trade items from the south to the north included macaw feathers, copper bells, and cocoa. A major trade item going from the Pueblos down south, and even reaching the Aztec/Nahua/Mexica peoples was turquoise. Some of the most famous examples of Aztec artwork featuring Pueblo-mined turquoised, that can sometimes be traced to particular mines.

It should be pointed out that many tribes, today and in precontact times, span the borders of US and Mexico. These include the Tipai and Paipai people in California and Baja California, the Cocopah people of the Colorado River, Yaqui, Tohono O'odham, Pima, Apache, Suma, Jumano, and Coahuiltecans. Tribal groups from California are visiting Baja California, and although they encounter language barriers today, they often know the same Bird Songs.

This is where the concept of Aridoamerica is useful, since it is the region between the US SW and Mesoamerica and is filled with its own tribes. The Aztec/Mixteca/Nahua people might have maintained trade with SW US tribes, because they originally migrated from the northwest (possibly around the Colorado River) and speak a Uto-Aztecan language, that is shared today numerous tribes including the Hopi, Tübatulabal, Shoshone, Paiutes, and many others.

Yes, it is well proven that Indians across the present day southwest traded with societies in present day Mexico. The most obvious example of this is maize/corn, which originated in Mexico and eventually became a staple crop across the Americas. Native Americans across North America were involved in continent wide trade networks.

There have been some (very few... perhaps one?) Maya objects found in archaeological sites in Florida. They may have been transmitted from hand to hand around the Gulf Coast, or some intrepid sailors may have crossed the 80 or so miles from Cancun to Cuba (which seems to have gone on(pdf)) and then the 90-some miles from Cuba to the Keys and further north (which is... speculative), or some combination of the two.

There was some talk about a Mayan connection to the Miami Circle - the stone circle found carved into the limestone near the mouth of the Miami River in the heart of downtown Miami. These folks (pdf) were pretty sure stone tools found at the Miami Circle were not Maya-made... but came from rock from central (Macon-area) Georgia. Which is actually kind of more remarkable, in some ways, since that's actually a longer distance to travel as the crow flies.

The thing I'm remembering came from further north, around the Tampa or Crystal River area... but it was isolated (not a lot of artifacts) so not part of a highly developed trade route. Probably the Apalachicola canoe mentioned in Canter's article (the "Cancun to Cuba" link).