In most stuck in snow situations I can think of, help shouldn't take long to get there -- stay with the vehicle! There might be situations though...
The "I shouldn't be alive" episode described them going so far off the track (closed highway I think) that nobody passes by with any regularity. In that case, you should probably stay with the vehicle as long as you could...
Couple of things you might consider....
-Knowledge of your environment. Evergreens nearby? Useful for insulation and more!
-Ice scraper. Goes without saying of course <img src="/images/graemlins/smile.gif" alt="" />
-Road flares. They can be used for signalling, and firestarting. Sometimes it's too darn cold and/or windy to be fiddling with magnesium shavings and ferro rods!
-A decent knife (big enough to baton and do other fun things with)
-High visibility signalling devices - VS-17 panels, glint tape, food coloring, whatever. If you're way off the beaten path, it may help attract the eye against the snow.
-2 way radios/walkie talkies - These aren't that expensive these days... you can find a set from $18, and for $50 you can get a set that picks up NOAA weather and has all kinds of nifty features. You shouldn't leave the vehicle, but if you do and have a passenger, it's good to be able to keep in touch in case you get seperated.
-Spare batteries for flashlights and radio
-DUCT TAPE! A whole roll. You can make snowshoes if you use a little ingenuity and some evergreen branches or other field expedient things. You can use it to tape up plastic and block the wind coming through a broken window or something, etc. Uses are everywhere, as always.
-Metal cup suitable for melting snow for drinking water
-Hand/Foot warmers, chemical. These can last 8-12 hours, depending on the brand. They're cheap, and you can buy a bunch.... expose them to air and they warm up. You can use them in enclosed spaces, and while you're asleep, unlike some open fire. Sure beats frostbite if you've got to leave the vehicle.
-Newspaper. One of chris's idea, lots of uses. Splints, insulation, etc
-Cooler - You can keep smaller things like batteries in there, and they won't freeze as quickly. Maybe even throw in a foot warmer described above, and things will stay toasty....
-Medical gear, including space blanket, splints, chapstick, etc
Others have already mentioned things like 2 x 4's and shovels and so on.
You also might consider...
CB Radio. Hooked directly to the battery, you can run it even if the car is shut off. Doesn't require a licence.
Winch - Helps ya get unstuck, if you've got a friendly tree or something similar nearby
Tow cables/chain/rope