Stone is stone-like. It's grey.
You'll either find it in cliff-faces or under a few meters of dirt. You can't mine it by hand though, you'll need a wooden pick, which you can craft from wood, which you collect by punching tree trunks. Here's the crafting chart
to explain all the different tools and how they're made.
Certain resources can only be found at certain levels (diamond, gold and others are very deep under the surface), and snow and ice only exist in snow biomes, but other than that you should be able to find everything else anywhere in the world. Except for blocks native to the Nether realm, but if you're just starting out you shouldn't be thinking about going to the Nether yet.