I use a kodak playsport. I think you can still get them for about £70. It does HD video and is completely waterproof, I use it for some nice underwater shots. I have it in a little pocket on my rucksack strap, and it's never had an issue with the cold. However it's 5mp stills are not great. But I am willing to use it in any conditions, so it's captured some extreme weather.
For proper photos, I have a Canon 7D DSLR in my bag. It's really heavy, but all metal, so can stand a bit of abuse, and frequently spends 10mins sat in the snow for a time lapse shot.
My main advice is that anything with a clever electronic zoom is not going to like cold ice, and wet, and will fail as my panasonic lumix did after 6 months.
I have started using my iphone 5 more, as it's much better quality than the kodak. for photos and videos. I use one of these to keep it safe.
http://www.lifeproof.com/shop/us_en/iphone-5/iphone-5-caseSo technically I take 3 cameras! But taking good photos and video is a big part of it for me.