This question is answered using three bits of knowledge:
1) Under pressure, the ice melts to form a layer of water which is eventually the reason why ice is so slippery. (There is a middle ground between the cause and effect which has to do with the anomalous behaviour of water between 273K and 277K. There is a video by Richard Feynman where he discusses this to some extent.))
2) The force applied by your feet on the ice is actually proportional to the tangent of the angle made between you foot and the ground between each step. Furthermore, in order to reduce the force per unit area applied by your foot on the ice (which thereby causes the ice to melt and thereby reduces the friction), you need to place your entire foot at once, flat, on the icy ground.
3) Furthermore, you do not want to separate your legs too far wide because this will lead to a slipping force on your back leg.
So, having taken all these three points into account - what you need to do is place your foot flat on the ice without separating your legs too much. Which in other words means that you take small steps and walk like a penguin unless you want to risk a bad fall.