I don't have any expertise in this field, and the question doesn't provide much detail about what sources Harari may be citing. I did a quick search on Google Books but find no reference to malnutrition in Sapiens. However, just glancing at a few sources we can see that bioarcheologists look at a wide range of evidence to reconstruct pre-historic diets and nutritional status, including:
- Human teeth: These may show signs of wear from eating fibrous plants. Microscopic layers in baby teeth indicate how old they were at time of weaning, and can also give insights into the nutritional/health status of the mother during pregnancy.
- Human bones: These can indicate a lot about the overall health of a person. Stunting of growth is usually a sign of malnutrition, especially when this is supported with other evidence.
- Animal bones: These can indicate what animals people were using and how they were using them. Obviously if people were eating less meat, we would expect to find less bones of the relevant animals.
- Pollen: General presence of pollen in a certain layer indicate what plants were present in the environment. Concentrations of certain kinds of pollen in human living areas may indicate use of that particular plant for food.
- Human coprolite (fossilized feces): Analysis of pollen and other things inside these may directly indicate what the person was eating.
One of the most powerful and widely-used tools across all forms of evidence is isotope analysis. Measuring different isotopes of carbon, nitrogen and sometimes other elements allows researchers to trace all kinds of connections between different organisms and what they are consuming through their fossilized remains.
I'm guessing Harare may be looking primarily at the Fertile Crescent, but a lot of what comes up for me with a quick search is focused on Europe. The article "Neolithic transition in Europe: The challenge for bioarchaeology is fairly broad and not focused specifically on nutrition, but relevant as an overview. "From Health to Civilization Stress? In Search for Traces of a Health Transition During the Early Neolithic in Europe" relies primarily on human skeletons to find evidence of malnutrition among other things. "Health Status of the Neolithic Population of Alepotrypa Cave, Greece" is especially relevant and also focuses on evidence from human skeletons. The abstract gives some technical detail on evidence of malnutrition: "anemic conditions (cribra orbitalia and porotic hyperostosis), mild or healed in manifestation, most probably of nutritional origin, resulting from a poor diet focused on terrestrial resources such as domesticated cereals".