The term does indeed trace its origins to Moses, with the tablets inscribed by the finger of god.
The term is quite obvious in meaning. It means something that is unchangeable and timeless. Until recently, carving stone, especially words in stone, was a very difficult process involving hammers and chisels. Once it was 'in stone', it was there and could never be removed.
(of course, now-a-days, you could just use a plasma-cutter or a krypton laser to plane away the surface of the stone tablet until the letters disappeared, but that is surely not the point, is it?)