I took a piece of foam out of an old beach mat and then sewed it inside of a small piece of nylon. It weighs 47g and is often a luxury I will take along. You can not only stuff clothing in a stuff sack, btw, you can also stuff natural materials. If you find a nice patch of dried grass/reeds/moss, it only takes you a few minutes to fill up a sack, and is more comfortable than you might think.
There is also another great system of temporary pillows, but it requires the right location and timing. If you make camp in a very mossy area (plenty of that here in Sweden), and you also have to make a cat hole to take a dump, here is what you can do:
1. Cut out a small rectangle of nice, soft, living moss. Don't use your knife in case there are rocks under it, you don't want to dull your blade. Just use a stick or your hand.
2. Move the moss patch aside, dig up your cat hole, and then take a dump.
3. Cover the dump with dirt/leaves/etc.
4. Take the moss patch back to camp and use it as your pillow. You can put it in a stuff sack, plastic bag, or just put it under your sleeping mat/ground cover.
5. The next day, after you break camp, go back to the spot where you took a dump and put the moss patch back.
The moss patch should grow back. I have returned to the same spots to make camp and checked, and sure enough, it looked just the way it did before I cut out the moss patch. So don't cry hippies, it's all good. ;)