Technically, coal could be formed by any type of organic matter. Organic matter includes stuff that is alive or used to be alive, including plants, animals, bacteria, insects, etc. One reason why coal deposits are formed from dead plant material is that there are simply way more plants than animals on land. (In the ocean, it is quite the opposite!)

If you cut down all the trees, ripped out all the grass, gathered up all the dead leaves, etc. and put them in a big pile, it would completely overwhelm a similar pile composed of all the animals, bacteria and bugs from the earth's surface. There was a point in the earth's history known as the Carboniferous period about 354 to 290 million years ago, when a lot of the coal and oil deposits we are mining today were formed. During this period in time, many regions of the earth's surface were covered with plants, almost like a continuous jungle. These plants were vascular plants with no seeds, but only because angiosperms (vascular plants with seeds) hadn't evolved yet. The climate was warm and humid, and the plants flourished. In fact, in many regions that plant material piled up and formed a wet organic mulch (remember that the climate was a lot more humid). When plant matter sits in wet soil, bacteria and other organisms that eat leaf litter (worms, insects) can not decompose it as well. The decomposition process, which converts organic matter to carbon dioxide, requires a lot of oxygen and oxygen becomes used up quickly in water-logged soil.

In the Carboniferous period, the bugs and bacteria and worms simply could not use most of the dead plants that piled up on the forest floor, so the organic matter became what we call peat. (Think of peat bogs, swamps and the muck on the bottom of rivers!) If peat becomes buried way underground, it slowly undergoes a chemical processes that turns it into hydrocarbons, which is what coal and oil are made of. These chemical processes are a result of extreme pressure and heat, such as you would expect if material was compressed under a lot of rock or water. So how does the peat become buried?

If a river changes it's course, it can deposit a lot of material over an area with time. Similarly, if a lake or an ocean forms over an area with peat, the peat will most likely become coal given enough time. A large part of North America was under oceans during this period. Coal is almost certainly forming today, perhaps in the peat bogs in England and Scotland. It is important to remember, though, that coal takes a very long time to form from peat because the peat has to become very compact. It is estimated that for every 1 vertical foot of coal mined from Kentucky, it took 10 vertical feet of original peat material to produce it.

Coal is mainly out of plant material, but not exclusively. You need a lake, protected from waves and oxygen (almost not air inside the water) and lots of plant and animal material to form coal. After forming this swamp, the organic rich soil must be buried in the sub-surface and submitted to high pressures and temperatures. Once that has happened the conditions for coal formation are there.

Plants are made up mostly of Carbon(C), Oxygen(O) and Hydrogen(H), although small amounts of other elements are present. In a live plant the C,O and H combines to make various organic molecules, but when a plant dies, eventually the O and the H escape and only the carbon remains. It is a bit like burning cellulose (say newspaper) and the RESIDUE is the pure soot = carbon. So the same thing happens but it takes longer because the reaction that sends of the H and the H runs slow at room temperature unlike the case when you burn it.

Because there is little oxygen in swamps and bogs, plant matter that dies does not decay (no animals can eat it) and instead gets buried, ultimately being pressed into very dense, heavy material. Once deeply buried, this matter is subjected to the heat within the earth as well as the pressure of being buried under kilometers of rock. This causes the structure of this material to become even further compressed into a material we call coal.

Most of the continents in the Carboniferous period (about 350 to 300 million years ago) were covered by seawater deep enough to turn much of the land surface into swamp. The reason why horsetails, ferns, club mosses, etc. are the plants that lived in these swamps is that plants that produced seeds had not yet evolved.