The cuisine of the Karankawa people is actually recorded somewhat decently, believe it or not. While there are some interpretive issues when Europeans describe them eating their meat "half-raw", for which we can probably say is a variant of rare or medium-rare rather than actually half-raw, the actual content of their diets is fairly well-known for a tribe that, otherwise, has been left in a more obscure place, which has gone extinct, and which was entirely non-agrarian and, rather, was seasonally nomadic. Seasonal nomadism could also be called seminomadism, but to my understanding, the latter implies something with regards to at least a bit of agrarianism, which they adamantly refused to pick up on.

So, Karankawa cuisine consisted of various things. While on the mainland, they hunted for venison and buffalo and even bits of poultry. On the islands, they would eat up oysters and fish. It is said that venison was the foremost component of their diet generally, though, and we hear about how they prepare it. Like many cultures historically, the Karankawa were known to put their meat in a boiling pot of water, letting the water cook indirectly. Though they did also sometimes stick it on a stick and roast over a fire, these were generally unspiced. The flavors that they had, they added to the water, which would then soak into the meat.

So, you might be asking - what flavors could they possibly get? Well, Cabeza de Vaca acting as a trader found that the mesquite bean was highly prized among them, and later records tell us they most certainly used it in flavoring. In fact, they even made a sort of bean-meal out of it. They were also known to utilize "Bamboo Brier", Aralia nudicaulis, also called "Wild sarsaparilla". One William Bollaert gives the following account:

"The Carancahuas boil the tender offsets of it - bruise and then cut it up into thin slices - then beaten up paste into a paste made for cakes - dried in the sun - and heated on a fire when eaten".

Much like the mesquite beans, the wild sarsaparilla had other culinary uses beyond flavoring the meat in a boiling pot. He wrote this between 1842 and 1844, quite late in Karankawa history, and well after a report from Lafitte's camp about a Cajun woman hooking up with a Kronk medicine man, only to run away because she found their food too boring, too bland.

The thing to consider in all of this is that they're pulling from all-natural ingredients, either local or traded for within a reasonable distance. There are plenty of roots and berries in Texas that they could've gone for, but mesquite and sarsaparilla are the ones most discussed in my sources - while others are left vaguely categorized as "berries", "roots", "plants", describing how they gather but not what they gather. Anything that could be made into meal or paste, have oils or juices extracted, or could be dumped into water and the flavor would naturally come out, would be a likely contender for use in their very non-standardized, non-formalized diet.

They may have also had some more 'exotic' flavors. While they lived quite close to what's now Mexico and there was a lot of bleedover of flavors between Coahuiltecos and Karankawa, and perhaps even the Chichimecas, the Karankawa also had a distinct word for tortillas native to their language that implied they were familiar with the Mesoamerican product. Indeed, they were known to trade for cornmeal and tortillas with peoples from modern Mexico, and to make their own tortillas from cornmeal acquired from nearby Caddoan peoples. Yet another hint at a possible connection is that they had a word for a flat pan, Kolame, which historical observers thought might be a Nahuatl loanword - the Nahua term for such a thing being Comalli.

Another thing they took from Mesoamerica? Chocolate.

Yes, as it so happens, there was wild, or perhaps feral, chocolate growing along the Texas coast historically. I believe I recall that in my readings, Tlaxcaltec missionaries tried to set up chocolate plantations, but separate mentions exist of it as well. It is mentioned in 1825 by one Jose Antonio Diaz de Leon: "...these are the lands which they have possessed by natural right; which includes the wild growth of the herb which they call chocolate, and which they use daily for their sustenance." Keyword: 'wild'. While the phrasing makes this sound a bit suspect, since he says "the herb they call chocolate" instead of just "chocolate", it would not be the first instance of chocolate turning up north of the Rio Grande, and the weather of the Gulf Coast might be able to grow it in some capacity at any rate. Other candidates, such as the Chocolate Flower, grow only in the extreme west of Texas. My research is failing me in trying to find any alternative solutions, so I can only conclude it was, indeed, some form of chocolate.

At any rate, this isn't a comprehensive list of Native American cuisine really, but it should provide an idea for how it all worked. For the Karankawa, they picked essentially whatever was edible, and favored particular items that are still popular flavors today. All sorts of things can be found, and just about all of them might've been used at one point or another - but taste is taste, and so the stuff that tastes good is what they hook onto.

I'm not a historian (though it is what I got my degree in), but I do work on native plant conservation and propagation in the eastern US and have a particular personal interest in the history of our native plants and their ethnobotanical uses so I think I have some relevant expertise to add here.

In addition to the filé powder mentioned by /u/highdesertwriter dervied from Sassafras albidium, native to the eastern US, native peoples here had access to other plants that they likely used for seasoning, teas, and medicinal purposes.

Spicebush, Lindera benzoin, was used as a seasoning by Ojibwa and Iroquois peoples and was also used by Americans when allspice was scarce (Tucker, 1994).

Toothwort, Cardamine concatenata, is a small spring ephemeral common across the eastern US and forms a small tuber that vaguely resembles canine teeth -- hence the name. The flavor is similar to horseradish. The related Cardamine diphylla was also consumed as a potherb or eaten raw.

The roots of Solomon's Seal, Polygonatum biflorum, were ground and used as a seasoning by the Cherokee. (Perry 1975)

While it's unlikely that Native Americans made great use of maple syrup ethnobotanist Huron H. Smith in the 1930's documented the Potawatomi using maple sap as a seasoning for meat and for creating a vinegar.

A great number of native ramps/wild onions/leeks Allium spp. were widespread and available to Native Americans.

There's evidence that dried hackberry fruit, Celtis occidentalis and potentially also Celtis tenuifolium, were used by the Lakota as a seasoning powder for meat.

In the southwest, there's evidence of native sumacs, Rhus spp., used as seasonings similar to how Rhus coriaria is used in middle-eastern cuisine. I don't know whether eastern North American sumacs like Rhus aromatica* were used as seasonings or not, but they were used to brew citrus-y teas.

My understanding is it's harder to track how wild plants were used compared to cultivated varieties because there's no way to track their use through tracking changes in their forms. That is, botanists and historians can make educated guesses about when corn became domesticated because humans selected for larger seeds, but wild-harvested species didn't see the same selection pressures. Hence some of the difficulty establishing what wild plants were used and what ways.

There are, however, a wide variety of native fruits and nuts in the eastern north american that were tasty and likely widely consumed, many of which are still eaten today. Many variety of fruits such as grapes (fox grapes, muscadines, etc.), cranberries, blueberries, huckleberries, raspberries, blackberries, dewberries, American persimmon, pawpaw, strawberries, cherries, plums, elderberry, red mulberry, maypops (native passionflowers), and serviceberry are all relatively widespread and most are edible without any processing. Native nuts like hazelnuts, black and white walnuts, hickories (including the pecan), and acorns, American chestnut before the blight, and chinquapin would also have been readily available in season and either immediately edible or edible with some processing.

Liberty Hyde Bailey a late 19th century/early 20th century botanist makes note in his preface to The Evolution of our Native Fruits, "...the present importance of our native fruits, both as subjects of historical inquiry and as elements in our national wealth, is not appreciated by European writers. In support of this statement, I have only to quote these sentences from DeCandolle's 'Origin of Cultivated Plants' (page 448): 'A noteworthy fact is the absence in countries of indigenous cultivated plants. Fore instance, we have none from the arctic or antarctic regions, where, it is true the floras consist of but few species. The United States, in spite of their vast territory, which will soon support hundreds of millions of inhabitants, only yields, as nutritious plants worth cultivating, the Jerusalem artichoke and the gourds. Zizania aquatica, [wild rice] which the natives gatehred wild, is a grass too interior to our cereals and to rice to make it worth the trouble of planting it. They had a few bulbs and edible berries, but they have not tried to cultivate them, having early received the maize, which was worth far more." So there does seem to be have been some bias by European writers to overlook or even denigrate the foodstuffs available to native peoples in Northern America as you suggest.

edit: We do have some records from plants introduced to Europe from America before 1600. In particular, I'd recommend Thomas Harriot's A Brief and True Report of the New Found Land of Virginia in 1588. If you have difficulty parsing the names he uses, A Short History of Botany in the United States from the 11th International Botanical Congress has a section that covers the names used by Harriot as well as those from early accounts by John White in 1585, and John Gerard in 1599.

A letter from botanist John Bannister to Dr. Robert Mirison from 1679 is also fascinating for recounting various native species that were used by Native Americans and colonists as foodstuffs. Discussions of spices and seasonings are mostly absent and there is probably already some confusion of Morus rubra and the introduced Morus alba and Morus nigra that had been an early introduction to the US. Still, he recounts several varieties of corn, various tubers, and serves as a testament for how rapidly important plants were moving into the Americas from the old world including various melons likely introduced via the slave trade from Africa and from Spaniards in Mesoamerica, sweet potatoes originally originating from Peru and Ecuador and likely first encountered by Europeans in Hispaniola.