You can find this ochre rock in the "striped" Canyons, where it is one of the most commmon types of canyonstones. Under the Sand of Dunes there is often a thick layer Sandstone instead of common Dirt.
Sandstone can also be found in older worlds created before R14 in the shape of cliffs and mountains not related to any canyons.
Different from canyonstones (Canyonstone, Ruddy Canyonstone, Dark Canyonstone) you will not need any Power Cells to mine this rock.
Sandstone is necessary for crafting Smooth Sandstone that looks a lot like Sand; the according rare Recipe can rarely be found in all kinds of Treasure Chests that randomly spawn in darkness.
When Sandstone is placed as it is, Dustevils can spawn on or near them during the (ingame-)day, also - more rarely - Trogs or even Dried Leafis, sometimes also ordinary Leafies, while Night Leafies and Night Pigsies might appear during the (ingame-)night.
This can also happen on older worlds that were created before Trogs, Dustevils and Dried Leafies had even been introduced.
Also Wood Treasure Chests might appear at night on this kind of block in completely dark areas, no matter where these blocks have been placed.