They ate stuff they brought with them. As they are about to leave the Tower of Cirith Ungol and entering Mordor, Frodo jokes:
I can't go all the way at a run, Sam,' said Frodo with a wry smile. 'I hope you've made inquiries about inns along the road? Or have you forgotten about food and drink?'
'Save me, but so I had!' said Sam. He whistled in dismay. 'Bless me, Mr. Frodo, but you've gone and made me that hungry and thirsty! I don't know when drop or morsel last passed my lips. I'd forgotten it, trying to find you. But let me think! Last time I looked I'd got about enough of that waybread, and of what Captain Faramir gave us, to keep me on my legs for a couple of weeks at a pinch. But if there's a drop left in my bottle, there's no more. That's not going to be enough for two, nohow. Don't orcs eat, and don't they drink? Or do they just live on foul air and poison?'
'No, they eat and drink, Sam. The Shadow that bred them can only mock, it cannot make: not real new things of its own. I don't think it gave life to the orcs, it only ruined them and twisted them; and if they are to live at all, they have to live like other living creatures. Foul waters and foul meats they'll take, if they can get no better, but not poison. They've fed me, and so I'm better off than you. There must be food and water somewhere in this place.'
'But there's no time to look for them,' said Sam.
'Well, things are a bit better than you think,' said Frodo. 'I have had a bit of luck while you were away. Indeed they did not take everything. I've found my food-bag among some rags on the floor. They've rummaged it, of course. But I guess they disliked the very look and smell of the lembas, worse than Gollum did. It's scattered about and some of it is trampled and broken, but I've gathered it together. It's not far short of what you've got. But they've taken Faramir's food, and they've slashed up my water-bottle.'
as they are working their way northwards from Cirith Ungol, they ate
Sharing a wafer of lembas, and munching it as best they could with their parched mouths. Frodo and Sam plodded on.
then they found
Water trickling. Out of a gully on the left, so sharp and narrow that it looked as if the black cliff had been cloven by some huge axe, water came dripping down: the last remains, maybe, of some sweet rain gathered from sunlit seas, but ill-fated to fall at last upon the walls of the Black Land and wander fruitless down into the dust. Here it came out of the rock in a little falling streamlet, and flowed across the path, and turning south ran away swiftly to be lost among the dead stones.
...The water was cool but not icy, and it had an unpleasant taste, at once bitter and oily, or so they would have said at home. Here it seemed beyond all praise, and beyond fear or prudence. They drank their fill, and Sam replenished his water-bottle.
Later, they ate and drank again
There they sat and made such a meal as they could. Keeping back the precious lembas for the evil days ahead, they ate the half of what remained in Sam's bag of Faramir's provision: some dried fruit, and a small slip of cured meat; and they sipped some water. They had drunk again from the pools in the valley, but they were very, thirsty again.
They hoped (mostly in vain) to find food and water in Mordor:
'I don't like the look of things at all,' said Sam. 'Pretty hopeless, I call it - saving that where there's such a lot of folk there must be wells or water, not to mention food. And these are Men not Orcs, or my eyes are all wrong.'
Neither he nor Frodo knew anything of the great slave-worked fields away south in this wide realm, beyond the fumes of the Mountain by the dark sad waters of Lake Núrnen; nor of the great roads that ran away east and south to tributary lands, from which the soldiers of the Tower brought long waggon-trains of goods and booty and fresh slaves. Here in the northward regions were the mines and forges, and the musterings of long-planned war; and here the Dark Power, moving its armies like pieces on the board, was gathering them together.
By the time they were ready to strike east towards Mt Doom, Sam said
'Well, to say nothing of water, we've got to eat less, Mr. Frodo, or else move a bit quicker, at any rate while we're still in this valley. One more bite and all the food's ended, save the Elves' waybread.'
A little later
He gave Frodo water and an additional wafer of the waybread, and he made a pillow of his cloak for his master's head. Frodo was too weary to debate the matter, and Sam did not tell him that he had drunk the last drop of their water, and eaten Sam's share of the food as well as his own.
but then
to his delight he caught the sound of trickling. Clambering a few steps up he found a tiny stream of dark water that came out from the hill-side and filled a little bare pool, from which again it spilled, and vanished then under the barren stones.
Sam tasted the water, and it seemed good enough. Then he drank deeply, refilled the bottle, and turned to go back.
Sam realizes that they are in a hopeless situation for food:
It looks every step of fifty miles,' he muttered gloomily staring at the threatening mountain, 'and that'll take a week, if it takes a day, with Mr. Frodo as he is.' He shook his head, and as he worked things out, slowly a new dark thought grew in his mind. Never for long had hope died in his staunch heart, and always until now he had taken some thought for their return. But the bitter truth came home to him at last: at best their provision would take them to their goal; and when the task was done, there they would come to an end, alone, houseless, foodless in the midst of a terrible desert. There could be no return.
As they went east they had nothing left but lembas to eat, while water was very hard to find:
The lembas had a virtue without which they would long ago have lain down to die. It did not satisfy desire, and at times Sam's mind was filled with the memories of food, and the longing for simple bread and meats. And yet this waybread of the Elves had a potency that increased as travellers relied on it alone and did not mingle it with other foods. It fed the will, and it gave strength to endure, and to master sinew and limb beyond the measure of mortal kind. But now a new decision must be made. They could not follow this road any longer; for it went on eastward into the great Shadow, but the Mountain now loomed upon their right, almost due south, and they must turn towards it. Yet still before it there stretched a wide region of fuming, barren, ash-ridden land.
'Water, water!' muttered Sam. He had stinted himself, and in his parched mouth his tongue seemed thick and swollen; but for all his care they now had very little left, perhaps half his bottle, and maybe there were still days to go. All would long ago have been spent, if they had not dared to follow the orc-road. For at long intervals on that highway cisterns had been built for the use of troops sent in haste through the waterless regions. In one Sam had found some water left, stale, muddied by the orcs, but still sufficient for their desperate case. Yet that was now a day ago. There was no hope of any more.
Now heading directly towards Mt Doom,
Sam gave him a mouthful of water; only one more mouthful remained. He went without himself;
Afterwards had Gandalf not rescued them, even if they avoided dying in the eruption of Mt Doom, they would have died of thirst before they could have starved.
