Sandstone is a material found in the game since it was released. Currently it can only be used to build. It naturally occurs under sand layers in deserts, and on shores. It received a new texture in the 1.2 update, "to better match sand".
It can also be crafted out of 4 sand blocks in a 2x2 square shape.
|Wooden Pickaxe:||2 secs|
|Stone Pickaxe:||1.33 secs|
|Iron Pickaxe:||1 sec|