How did they originally figure out what parts of plants to eat?

I have eaten both carrot leaves and celery leaves by the way. I also eat the turnip greens and the cooked leaves of beans. You are certainly right about rhubarb though. We do have the ability to taste most of the serious toxins like most alkaloids and cyanide compounds which taste bitter. I made several slideshows on edible plants and toxic and lethal plants under the Youtube user name bob45ana. It is a question that I have spent a great deal of time thinking about.

We always ate some plants and must have learned from our parents. Some time in the last few million years our communication skills must have increased to the point where we could pass down much more accumulated knowledge. People who died from being poisoned passed down that a certain plant was deadly and it became widely known. That is a tough way to learn but it probably happened when times were desperate and people were forced experiment. It must have been tough to expand into to new territories like our ancestors did about 50,000 years ago. We didn't learn much from the Neanderthals because they were apparently almost 100 percent carnivores. That is probably why, in my opinion, that it took us so long to outcompete the neanderthals. Once we learned many of the new plants by trial and error and educated guesses, we had a much greater food base and our population expanded dramatically beyond what the Neanderthals could deal with. Every successful ancient population seems to have found crops that fill all the proteins requirements. They would plant corn and beans or rice and soybeans or wheat and chickpeas. The populations that had the best nutrition were the ones that prospered. Adding food plants probably was a rather slow process with some people getting sick along the way. Once someone learned a new plant, everyone in the region would learn about it.

I have read several articles on ethnobotany. They find mummies or frozen corpses like the iceman and figure out all the foods that ancient people ate. There was one guy who had something like 60 different kinds of seeds in his stomach. They also examined coprolites and archeological sites and ancients hearths. They could handle more toxic plants by mixing them up so that also greatly increased the amount of food available. That is dramatically different than when we became reliant on a few seed crops, typically a grain and a legume along with some kind of fruits and vegetables. The ancient people knew hundreds of different plants. Chimpanzees also eat hundreds of different plants and they often become ripe at different times and they have to know when and where to find them. Some people have speculated that our capacity to recognize leaves is why we are able to read. We have acquired the capacity by evolving the ability to instantly recognize hundreds of different leaves and fruit shapes.

Probaly Trial and Error