Locating sources for resources is a crucial step forward
Creating Building Blocks
Stone Blocks (not Cobblestone) are the preferred medium for building the walls of our compound and our proper home and castle - and to obtain them all that we need to do is start making use of the stacks of Cobblestone and Coal we have acquired by cooking the Cobblestone in the Furnace to turn it back into Stone.
The formula is one stack (x64) of Cobblestone plus x8 Coal. That will result in one stack (x64) of Stone Blocks. Repeat that until you have a proper supply of Stone Blocks to start building with, and then spend some time converting the area near your shelter into a nice and level building site. By the time this is done you will have mined tons of material and probably moved even more tons but the end result is a nice flat area to build on that offers you line-of-sight to keep you from being ambushed by mobs.
Building a secure home is Priority One
The Building Site
With the site cleared lay in the foundations and then start constructing the walls and finally the roof of your castle. You are going to need additional Wood Resources so you may as well harvest some of that in the process, and then get your doors and torches in place so that the interior of your castle (fortress, whatever, I call it a castle) is well lit and thus not a likely spawn point for mobs.
In addition to harvesting a few stacks of Wood you will also want to obtain a few stacks of Sand to turn into Glass or Sandstone and you will want to craft some Shears so that you can begin to harvest the Wool you need for making the Bed and some artwork to hang on your new walls.
If you see Pigs, kill them. You want to start stocking porkchops so you have food to heal with - don't take this wrong, Apples are great but nowhere near as easy to obtain as porkchops are! You should also be killing Chickens for their meat and feathers, and Cows for their Leather and meat. Try to harvest the Wool from Sheep rather than killing them...
While the game is fully functional depending upon the seed you end up with for your game things can get a bit wonky. For example if the seed your game creates is mostly hills and mountains, the animals can end up all in the ocean rather than on land, in which case you will need to kill them in the water and dive to recover their resources from the ocean floor. That can be a bit tricky but you will get the hang of it!
Resources like Coal are available above ground level as well
Once you have secured a supply of food head home and cook it then cache it in your storage, hit the bed and in the morning head back out and start walking along the shore until you find a Clay deposit and harvest some of that for making bricks. You also want to keep an eye out for a stand of Sugar to harvest.
Find a spot that is close to your base and plant the Sugar Cane you found in the sand along the water's edge and give it a few days to grow, making it a renewable resource rather than one you have to constantly hunt for. You can use the Sugar Cane for making Sugar and for making Paper, which you need to make Books, and then Bookshelves, which are a great decoration for your base.
Eventually you will work your way through the available wood resources and thus will no longer be in a position to replace tools and torches, but by that point you should have a plentiful supply of every resource except Diamonds, but that still makes for a good first mining run. With those resources safely stored in your Chests, it is time to prepare for a return to the overland.