Well, i know to dig myself a little hole in a hill first off around nearby trees... So, i've got a base.
I also dug down into a cave and provided a means to get back up and a map in case i get lost.
(I couldn't resist going into creative to get the map and the ladders... I'll probably get a horse when i dry the caves up...)
I've also murdered a few cows on the way and the trees seem to be giving me apples (Thank god...)
Go for iron armor first. You really only need the anvil when you have multiple enchanted items that you want to combine, or have enchanted books that you want to put on things; so go for the iron armor first.
Go for the armor first, NOT the anvil. You want to have a full set of iron armor. Trust me, the anvil will have no use at this point. It also helps to construct a bow. When you first enter the Nether, the bow will be your friend when taking out the ghasts, and when you fight blazes, you want to have at least a full set of iron armor, along with an iron sword. And take some food, because fire damage will do 1/2 damage regardless of armor (until you get fire protection), and you want to keep your food bar up so you can heal.
Like others have said, in Survival, you want to get iron armor and an iron sword ASAP. it's the best armor you can get early on.
Start breaking tall grass and get some wheat seeds, make a hoe (two sticks, two planks), till some soil with it within 4 blocks of some water and plant those seeds. Wait from them to fully grow (get golden brown) before you harvest them for wheat (and you'll get some seeds back to replant). Put torches around them to get them to grow faster. Make yourself some bread (three wheat) at the crafting table. Once you get yourself a wheat farm going, the food issue isn't so critical.
If you have carrots from a bonus chest or a NPC village, and haven't eaten them yet, plant those too. But if you don't have carrots, make bread.