Accounts by westerners enslaved by nomadic tribes (when they shipwrecked on the coast) often talk about looking for sand to sleep on, especially when in the rocky parts of the Sahara, so I’d wager humans have been sleeping on sand for a very long time.