Therese of Earth and Living figured out how to construct shoes like those worn by Medieval Scandinavians. It's not as simple as you might think, but it's a quite feasible craft project for the non-professional leatherworker. She provides step-by-step instructions with pictures from start to finish. Once you're done, grab a sword and go raiding!
Link via The Presurfer
I believe, though, that they are migration era Germanic, rather than Viking...
http://www.google.com/images?q=gillies+irish+dance+shoes
http://medievalmoccasins.com/