Avoid cotton anything. Like mentioned, polypro or polyester long johns work great and even insulate when wet. They wick moisture instead of soaking it up like cotton, which keeps it against your skin and could potentially cause you to get hypothermia. They hold odor pretty bad though. The military issues them in their extreme cold weather system (ecws), and you can get them at any army-navy/surplus store pretty cheap. Target has some that are 88% poly / 12% wool and they're pretty nice, but too pricey. Merino wool and silk are real nice, but hard to come by on the cheap. Although not long johns, old german military surplus pants are usually wool. cotton kills.
Walmart has a coleman fleece 'sleeping bag' that would actually work really well as a sleeping bag liner, around $16 I think. Or you could find those older fleece swiss military ones, even cheaper from most places. But honestly for your sleeping bag, you can't go wrong with lining it with a woobie blanket. It's the army issued poncho liner, best warmth to weight ratio. Those blankets in the backs of uhauls are easy to 'acquire', but they're pretty heavy. Harbor freight sells them pretty cheap too.
Size boots large enough to wear two pairs of thick socks. Always keep something on your head. Remember the saying, "Cold feet, put on a hat". Balaclavas are great when sleeping.
Emergency blankets are one of the best things to have in your pack, I keep two.
And also as mentioned, use a pad under your sleeping bag or bed roll. Those blue walmart ones or G.I. both work good, and are worth their weight in gold (there are lighter options, but more expensive). The cold ground or steel sucks the warmth right out of you.
I could go on forever, I love winter.