Sleipnir (pronounced either SLAYP-nur or SLEP-nur) was the mighty gray steed of Odin, the king of the Norse gods. Sleipnir had eight legs and was the fastest horse of all the gods or mortals. He had the ability to run not only on land, but also over water and in the air. This is why the runes making up Sleipnir's name roughly translate as a journey through ice, sun, trees and water.
As SigmaVirus documents above, Sleipnir's beginnings are odd indeed. A giant disguised himself as a mason and offered to build a wall around Asgard, the home of the gods. He bragged he could finish the wall in one winter with only the help of his mighty stallion, Svadilfari. In return for the wall, the gods were to give him the goddess Freja. The gods laughingly agreed, but over time they became concerned when it looked like the giant would actually finish his task. The trickster god Loki took the form of a mare and enticed the stallion to stop working on the last day of winter. The wall was not finished and the giant revealed himself in his anger and was killed. Several months later Loki returned to Asgard leading a colt he called Sleipnir. He presented the horse to Odin:
"'Take him!' said Loki. 'I bore him and he'll bear you. You'll find he can outpace Golden and Joyous, Shining and Swift, Silver-Maned and Sinewy, Gleaming and Hollow-hoofed, Gold Mane and Light Feet (the mighty horses of the gods and giants), and outrun whatever horses there are in Jotunheim (the realm of giants). No horse will ever be able to keep up with him.'"
Besides running through water and air, Sleipnir could also easily move between the Nine Worlds inhabited by the gods, giants, man, and elves. On two occasions he traveled into Niflheim, the forbidden lands of the dead. Once Odin, concerned about his son Baldur's visions of his own death, traveled on Sleipnir to visit Hel, the goddess of Niflheim. Later when Baldur had fallen, Hermod, Odin's other son, rode Sleipnir back into the depths of Niflheim to attempt to resurrect Baldur.
On the day of Ragnarok, Odin rode Sleipnir into battle with the Fenris wolf. There Odin was swallowed by the wolf and perished, but the fate of Sleipnir was unknown.
Where did the idea of a horse with eight legs come from? One possibility lies with a unique Viking horse that was bred in Iceland. These horses have two unusual gaits called "Tolt" and "Flying Pace" which can give the illusion of a horse running with eight legs. Another possibility is that the eight legs are merely symbolic. Vikings thought of horses as symbols of death and horse bones were often found buried in graves. Therefore, Sleipnir's eight legs may represent the eight legs of four mourners that commonly carried a casket as clampe notes in his writeup above.
Interestingly, Odin and Sleipnir may have inspired the legend of Santa Claus. The Norse people thought that Odin and Sleipnir rode through the sky during the winter solstice. Children who left hay and sugar for Sleipnir were rewarded with gifts. Over time bearded Odin morphed into Santa Claus while Sleipnir with his eight legs turned into the eight reindeer pulling Santa's sleigh. Children today leave out cookies and milk for Santa, in the hopes that he will bring them presents.
Quote and other info from "The Norse Myths" by Kevin Crossley-Holland