Potatoes may be indigenous to Middle-earth or perhaps they were brought there from somewhere else.
Potatoes can be boiled, mashed, or stuck in a stew as Sam preferred and served with other foods such as fish and rabbits and are especially good with herbs and spices.
Sam explains this to Treebeard when Gollum asks what it is which he describes as liking to use to make chips to cook with fish when he, Frodo Baggins and Gollum were in Ithilien. Back in the Shire, Sam's father, Hamfast Gamgee, was an acknowledged expert in growing the "taters."
In the films, the talk between Sam and Gollum also takes place.