For most players, the primary usage of finding fossils is to get the mass amount of bone blocks that fossils generate with. This can be especially useful if playing on peaceful difficulty, as skeletons won't be able to spawn, meaning that bones are much harder to acquire. Fossils also generate coal ore, although if you want to find coal ore, it is much easier to just look in a cave. However, if you do come across a fossil and mine it for the bone blocks, it's worth it to mine the coal ore. Coal is very helpful, as it can be used to make torches, or used as fuel.
A bone block by itself has no use, except for the fact that if a note block is placed on top of it, the note block will have a xylophone sound. However, a bone block can be crafted into bone meal, which can be used for many purposes. Anything that can be dyed, including banners, terracotta, stained glass, shulker boxes, firework stars, concrete powder, and beds, can be dyed white with bone meal. In addition, bone meal can be combined with other dyes to make secondary dyes, including gray, light gray, light blue, lime, magenta, and pink. One of the most common and beneficial uses of bone meal, is to use it as fertilizer, to grow crops, trees, or create tall grass and flowers if used on grass blocks.
Finding the right place to mine
The most important thing when trying to find fossils, is to mine in the right biome. Here is a list of the biomes that fossils can spawn in:
When finding a spot to mine, it's also recommended to mine in a larger biome, so that you have more room in the biome you're in. For example, if you find a swampland or desert biome but it's only 1 chunk wide, that's only 1 chunk of mining space, and it is very unlikely that a fossil will generate in that 1 chunk.
Once you find a spot to mine, it's time to start searching for fossils. You can do this by either caving or mining. Note that fossils will only generate 15 - 24 blocks below the surface, so make sure to always look here.
Caving has nearly the same advantages and disadvantages as it does when mining ores. Caves have lots of exposed surface, which saves you a lot of time and tools by mining. However, it is very likely that caves will be either shallower or deeper than fossils generate, and it is also likely that the cave may lead out of the biome you are mining in.
When caving, always be on the lookout for a bone block, as many times only 1 block will be exposed. Also, if you are in the correct Y coordinates (about Y = 40 - 49, a bit lower for land below sea level, and a bit higher for land above sea level), mine as much coal ore as possible, as it is possible that it is part of a fossil. This particularly goes for if you only see one coal ore, as more than one coal usually do not generate next to each other in fossils.
Mining rather than caving can be useful if you don't want to deal with the monsters in a cave, want to collect lots of cobblestone while finding fossils, or want to make sure you are on the exact Y-coordinates for fossils.
Branch mining is a good way to mine when looking for fossils. Try to find a flat section of a swampland or desert biome. A flat section allows for branch mining without having to dig up or down. This is because where fossils are found in the ground does not depend on the Y-coordinate, but rather how far beneath the ground it is. Once you've found a suitable area, dig down about 20 blocks and start branch mining.
The basic branch mining mechanics here are the same as layout 2 for the branch mining mentioned in Tutorials/Mining. However, the tunnels feeding off of the long tunnel should be 6 - 8 blocks from each other, which could also be said as having 5 - 7 blocks in between them. For the best overall efficiency, make the tunnels with 6 blocks in between them, or 7 blocks from each other. There is only one type of fossil that generates smaller than this. All other fossils are at least 5 blocks wide on every side, making them able to be seen in tunnels that have 6 blocks in between them. If you want to make sure you get every fossil, make your branch mine tunnels with 4 blocks in between, or 5 blocks from each other. However, although you will see every single fossil there is this way, it is inefficient.
Other Mining Types
Other types of mining, including strip mining and speed mining, should usually be performed in the same way they would if looking for ores. However, note that they must be performed 15 - 24 blocks below the surface, as those are the only layers that fossils can generate in.
Once a fossil is found, dig all around it to make sure there is nothing dangerous. Fortunately, lava is the main concern when mining, and lava does not usually generate so high up in the world. Once the fossil is excavated, you may want to take a screenshot of it, as fossils are rather rare, and you may not encounter one again for a long time. Then, start mining the fossil. You can mine both the bone blocks and coal ore with any type of pickaxe, but if you use your hands, it will drop nothing.