First of all, coal is not just carbon. Coal is a mixture of complicated organic molecules derived from ancient plants, fungi, and bacteria. However, in the natural "maturation" processes of coal, heat and pressure change its chemical composition over time so that it becomes nearly pure carbon in the form of graphite.

The difference between graphite and diamond is in the three-dimensional arrangement of the carbon atoms in the material. Graphite is made of flat sheets of carbon atoms in a hexagonal arrangement. The sheets stack one over the other, with only weak interactions between sheets. Diamond is not arranged in sheets; instead, each carbon atom is connected to four others in a tetrahedral arrangement. It turns out that this arrangement is not as different from the structure of graphite as it sounds. If the sheets of graphite are compressed close enough together, the carbon atoms will be in just about the right position to make the bonds of diamond. In fact, at high temperatures and pressures, this indeed happens.
It goes the other way, too. It turns out that graphite is actually more stable than diamond at room temperature and atmospheric pressure. Unless the surface of a diamond is chemically stabilized, the diamond vill convert to graphite! Fortunately, fresh diamond surfaces are easily stabilized by reacting with whatever touched them, so this isn't likely to happen unless you carefully cut a diamond in a vacuum.