Our only references to potatoes by name come from the late Third Age, but they may have been known in Beleriand as early as the First Age. There are references from that period to a vegetable known as to the Petty-dwarves as 'earth-bread' that sounds remarkably similar to a potato, though the identity is not explicit.

Potatoes seem to have vanished from Middle-earth at some point after the Third Age (indeed it is hinted by Mím that Men would consume them completely if they knew the secret of 'earth-bread'). Whatever happened to them, there were no similar plants to be found in Europe until potatoes were introduced from the Americas in the sixteenth century (or perhaps 're-introduced', if they were indeed known in Middle-earth's earlier ages).

We only hear about literal potatoes from Hobbits (and indeed Samwise Gamgee's father Hamfast was held to be a particular expert on the subject). This surely does not mean, however, that potatoes were limited to the Shire, and indeed Sam fully expected to find them - or something like them - growing as far from the Shire as Ithilien.