from the peshat department
Yaakov arrives at some place en-route to Charan, and sets up a stone pillow for himself. This may seem like a strange thing to do - stones are not the softest things in the world, but on the other hand, it is not necessarily harder than the ground, and it elevates the head.
In Bereishit 28:11 we read:
יא וַיִּפְגַּע בַּמָּקוֹם וַיָּלֶן שָׁם, כִּי-בָא הַשֶּׁמֶשׁ, וַיִּקַּח מֵאַבְנֵי הַמָּקוֹם, וַיָּשֶׂם מְרַאֲשֹׁתָיו; וַיִּשְׁכַּב, בַּמָּקוֹם הַהוּא.
11 And he lighted upon the place, and tarried there all night, because the sun was set; and he took one of the stones of the place, and put it under his head, and lay down in that place to sleep.
It turns out that the ancient Egyptians, or at least some of them, used stone pillows. Well, not exactly pillows; they used a crescent-shaped headrest made of ivory, stone, or wood. One website I saw ascribed the use of stone headrests to ascetics only, but I don't know how solid that info is - from what else I've read it seems like it was more common.
Figure 1: wooden and stone headrests. (see more here)