Stone Shamanism refers to beliefs and practices followed in Shinovar by the Shin people, who consider it profane to walk on stone or use Stormlight for everyday illumination.
This seems to have something to do with the concept of Truthless. When a Truthless dies, Stone Shamans of Shinovar will come to reclaim his Shardblade. This implies that there have been other Truthless before Szeth.
In the Shin culture, those who add are to be revered; great people create food and clothing. Those who take away - warriors - those who kill - are considered the lowliest of Shin; they are traded and sold between houses, like slaves.
Men trade and sell them between houses by way of little stones that signify ownership, and any man who picks up a weapon must join them and be treated the same.