When you have trouble finding coal in "Minecraft," you can turn to its sibling instead: charcoal. Unlike coal, you won't find charcoal naturally occurring out in the caves; you'll need to smelt some wood inside of a furnace to yield charcoal, which in turn serves as fuel itself.
Making a Furnace
Bring nine blocks of cobblestone to any crafting table; cobblestone is what stone turns into after you mine it, so your bags will likely be full of it if you've done any exploring. Fill every square in the crafting table's 3-by-3 crafting grid with a block of cobblestone, except for the very center. This produces a furnace, an item that you can place and interact with the same way as the crafting table.
Interacting with the furnace brings up a screen with three boxes: two on the left side and one on the right side. The item you place in the upper left box is what you are burning -- place wood in it now. The lower left box is your heat source -- if you don't have any coal or lava buckets, you can use more wood as fuel. When the fire icon in-between the two boxes fills, a single piece of charcoal will appear in the box on the right side of the furnace screen.
Benefits of Charcoal
Functionally, there is no difference between coal and charcoal. Both are an equally powerful source of fuel and both can help create torches. The main benefit of charcoal is that while you need to find coal out in the wild, charcoal is available right from home provided you have some wood. However, there is one disadvantage: you cannot use charcoal to create coal blocks.