A studded tire and some longer cranks are what you need. A wide tire would help you float better and not get bogged down in semi-solid snow but you can only go as wide as your frame allows.
I find a 26" MUni with a 3" studded tire is awesome in winter. I also really liked using my 36 in winter. Big wheels roll and float much better in snow than smaller ones.
Here is a tutorial I wrote up abut making studded tires. Hope it helps.