Darkness is obsidian. Obsidian Pillars, Obsidian Dragons. Though jet or onyx would make more sense, since obsidian is a type of volcanic rock.
Personally I'd use bloodstone, a black gem with blood-red spots. Yeah, I know the real bloodstone (heliotrope) is green with red spots, but if it's dark enough it's black.