It depends on your anticipated conditions. If you're planning on off-roading in snow you need tires with fairly heavy lugs (though too heavy will just collect snow). For ice you definitely need metal-studded tires -- riding a bike on ice otherwise is like riding on grease.
If you ride mostly on roads that are fairly heavily traveled by autos the best choice is fairly smooth studded tires where the studs are on the sides but the middle is smooth. This way the studs engage when you lean at all, but don't seriously impede you when riding straight.
icebike.orgicebike.org has kind of fallen into disuse (the latest "news" is from 2006), but still has some good links.
