The scientific name of the plant is Amaranthus viridis, which tells us that it's a member of the large botanical family known as the amaranths. The amaranths are thought to have originated in the highlands of tropical North America, where they were a food source for Amerindians native to that region, such as the Maya. After Cortes' conquest of Mexico, Spaniards returning from the New World to the Old carried with them, among their treasures, newly discovered foods native to the Western Hemisphere. Chocolate, chili peppers, tomatoes and the domestic turkey were among Mexico's gifts to the kitchens of Spain, but so were plants like amaranth. Spanish and Portuguese explorers, colonists and slavers then carried amaranth on to Africa where it flourished and became part of the native diet.
When African slaves were forcefully brought to Brazil to work on sugar plantations and in gold mines, they brought their food traditions and their foods with them. Thus, amaranth recrossed the Atlantic ocean back to Brazil, where it became an integral part of the slaves' diet in colonial times. The route by which amaranth became part of Brazil's gastronomy, therefore, is a long one - Mexico to the Iberian Peninsula, to West Africa and finally back across the ocean to Brazil.
Because amaranth came to Brazil from Africa, not directly from Mexico, it is most strongly associated with the Afro-Brazilian cuisines of Northeastern Brazil, specifically in the state of Bahia where the African influence on cooking is strongest. In Bahia and neighboring states, the plant is normally called bredo in Portuguese. In other regions of Brazil it's better known as caruru. Confusingly, in the region where the term bredo prevails, there is a stew-type dish called caruru, made primarily with okra (quiabo) another vegetable import from Africa.
The plant's journey from Mexico to Brazil is not the only one it's made. From its Mexican origins, it has spread to India, particularly in South India, to Greece, and to the Caribbean, where the Jamaicans know it as callaloo. It has even become part of the Indian tradition of medicine known as Ayurvedic, where it is used as a medicinal herb.
Even though the plant has significant food value, it has adapted itself so well to soil and climate conditions in Brazil that many farmers consider it invasive - a weed. It has even successfully urbanized itself and knowing foragers often spot it growing in abandoned inner city lots or even in cracks in the pavement. The smartest of these foragers have discovered this bounty and are helping themselves to a free supply of the green.