Some stones were painted black with very finely crushed coal dust. I have one of them - it's named the Blackstone. The colour of the rock beneath is sandy brown. Black sandstone is called shale - it's soft and very crumbly.
Other rocks were stained with ochre. Much of it will have washed off by now.