I have done quite a bit of engraving on various stones types
all using a trend tungsten carbide router bit with replaceable tips 90 degree square tips..
sandstone dead easy
slate easy to hard
I've bought place mats and drinks coasters and they are easy to cut...Floor tiles from B&Q 13mm thick are very hard I cut them to size with a diamond tile cutting machine engraving them was hard but manageable and gives a good clear finish
Granite from old work tops cuts ok with a diamond 60 degree bit from ebay

hope this helps