A good shelter should protect you from the elements, ideally giving you enough protection that the calories (energy) you expend building it is more than saved by the ones you don't expand keeping warm. This might sound trivial, and it is. When it comes to practical implementations the issue becomes much more complex. What is sufficient in the summer in southern Georgia is most likely far to little for winter Greenland. And in the Empty Quarter of the Arabian Peninsula one needs to take yet another set of conditions into consideration. And under some conditions you will need a shelter to stay alive, since no ammount of shivering or exercise will allow a naked human to live long at -40 C.
For wind and rain protection one can use moss. Just carefully remove the mats of moss that is often formed on rocks and dead logs and place on top of your shelter. Not only does these mats improve your shelter, but they also camoflage it, should you feel the need of this. If you replace the moss before you leave the site it will live, thus being a low impact type of shelter material.
One important issue that is often overlooked is insulation between you and the ground. Under most temperate conditions this should be at least 16 cm (6"). If at all possible use dry materials (spruce, Picea sp., boughs are an exception to this, since they are better used fresh).
If possible you should try to build your bed above the ground. Use logs to make a bed, and cover it with insulating material.
Also remember that you can use fire, either directly or indirectly, to compensate for your shelter being less than ideally insulated. Examples of this is the fire-bed, the super-shelter, and the good old lean-to with a log-fire.
Another way to store and use heat is to use hot rocks. Simply take rocks of fist to grapefruit size and heat in the fire until they are hot to the touch (the "hot potato stage"), and place them inside your shelter. Of you have something to wrap them in (bandana, spare T-shirt, etc) you can keep them close to your body when sleeping.
If you have a metal cook-pot of some sort you can fill it with even hotter rocks, and place the pot inside your shelter, thereby giving yourself a "space heater". Just be carefull so you don't burn yourself.
Apart from common sense (such as not sleeping on ice, using sufficient insulation for the conditions, and trying to gain a bit of height over the surrondings), there are three important considerations when sleeping in the cold (-20 C to -50 C):
You will need a good insulating layer between you and the ground. The "classical" way to accomplish this the north of Scandinavia is the start with a layer of shrub or branches, then use various combinations of reindeer furs and modern closed cell foam pads. Personally I most often use one 14 mm thick closed cell foam pad and one reindeer fur, in that order, on top of the shrub layer (lots of shrub birch, there are very few pines or spruces on some areas once you reach the tundra).
If you get snow into your sleeping system, it will melt and become water, which in turn will make you cold. My solution to this is to use a bivy sack over my sleeping bag made from a thin cotton/polyester poplin. This will stop loose snow fairly well, but at the same time it will ventilate fairly well (see below).
Your body produces surprising amounts of water each day, water that will -- if closed in -- remain withing your sleeping system (and clothes), where it will eventually form a layer of ice that will strongly reduce the effectiveness of the garment or sleeping bag. Thus you should:
Some people use vapor barrier lines in their sleeping bags, and claim they work well for them. Personally I have never tried this, so I cannot comment.