I've started several fortresses now, and I've never encountered any lignite or bituminous coal. I've even prospected a couple maps (with DFHack) to see if it was merely out of reach, but unless prospect doesn't show these minerals, there has never been any in my maps.
Is this common, or am I doing something wrong?