As long as you're exploring the overworld, you'd regularly encounter groups of cows or pigs, which would give you ample amounts of food. Steaks and beef keep you full for a long time.
If you're spelunking in caves, then you would need to return to a base to drop off minerals every once in a while anyway. Why not grow food there? Even killed zombies sometimes drop food.
And if you're exploring the Nether... running out of food is usually the least of your worries. When you enter the Nether with exploration in mind, you should be prepared for a long trip.
Anyway, do anybody play any mods for Minecraft? I play Tekkit, and it's awesome in my eyes. Machinery, vast processing and sorting systems, easy ways to acquire building materials, extra ambient sounds, new content in the Nether, that nifty minimap...
The best ting is that the changes brought by Tekkit rarely kick in before you reach what can be described as "lategame" in vanilla Minecraft. To get anywhere with machines, you need lots of redstone, and to have automated mining, you need lots of diamonds. Once you've reached that level in Vanilla, all that's left to do is construction projects. In Tekkit, this is where the fun starts.
Oh, and that awesome feeling the first time a Creeper explodes in your face, throwing you against a wall... and dealing only a single heart of damage, because of that über-armour you've saved up for. Too bad Tekkit runs at Minecraft 1.2.5, though. No carrots, potatoes, item frames or Withers.