Here is the setup I used for my last snowshoeing trip. We set up the tent right on top of the snow, and I was perfectly warm. When I woke up in the am there was ice on the tent, and icicles inside from the moisture in our breath, but I was fine and warm. It boils down to this: a good tent (this wont work for stargazing obviously), a good bag, and a good thermal pad.

Tent: North Face Mountian 25
Bag: Moonstone Maxima 0deg bag
Pad: Thermarest

Clothing I wear for sleep: Thin set of capaleine long underwear, wool hat. Thats it. In my experience the more clothes you wear in your sleeping bag the more your body has expend energy to warm up the colder you will be. Of course if your bag is not suited for the conditions you will have to wear clothes.

All an air matress does is put a large volume of cold air right next to your body. Makes for a cold night.