The following are some constellations mentioned or refered to in the old Scandinavian poems. Unfortunatly, exactly which stars these stories refer to is unknown, so after the tale is told, I will explain which stars I think are being referred to.

Aurvandil's Toe
A brave warrior named Aurvandil was going about his travels far to the north. He came to an impassable river called Elivagar. Thor, the god of thunder, Offered to take him across the river by placing him in a basket. However, one of his toes stuck out and was frozen. Thor broke the toe off and threw it into the sky.
This tale is recounted in Snorri's Prose Edda. Since Aurvandil's toe was frozen and this episode takes place in winter, I would guess the Norsemen were referring to a blue star that appears predominatly in the colder months and didn't appear in to be in another constellation. My best guess is the bright star Sirus in Canis Major.

The Eyes of Thazi
One day the three gods Odin, Loki, and Hoenir were traveling. They stopped to cook an ox, but the fire wasn't getting hot enough. They found out it was because an eagle in a tree was preventing the flames from getting hotter, but he would allow the gods to cook their ox if he was allowed his fill of the meat. The gods agreed, and soon the ox was cooked. However, Loki thought the eagle had taken too much, and stabbed it with a stick as he flew away. But poor Loki was stuck! And the eagle carried the trickster god with him.

The eagle captured Loki and told the god that he was a giant named Thazi, and he would only grant him mercy if he brought him Idunna, the goddess who kept the Apples of Youth. Loki agreed, and soon he captured Idunna and brought her before the giant. Loki was freed.

With out the Apples of Youth, the gods grew older. When they found out Loki was behind this, they threatened to harm him unless he rescued Idunna. Lokie took Freyja's falchon cloak, turned into a bird, and went of to Giant Land. When Thazi wasn't looking, he changed Idunna into a nut and flew off with her. Thazi turned back into an eagle and followed them to Asgard, hom of the gods.

The gods were waiting in ambush. As soon as the eagle flew over the walls, the gods set a fire to burn his wings, and the giant was slain. However, his daughter Skaldi demanded compensation, so the gods allowed her to choose a husband from among them by looking only at his feet. She choose the Vanir god Njord. Also, the gods had to make her laugh, so Loki tied himself to a goat and the resulting dance caused the giantess to lauigh. Finally, Odin took Thazi's eyes and placed them in the sky as a constellation.
This story is also found in The Prose Edda. However, according to the eddic poem Harbard's Song, Thor takes credit for placing Thazi's eyes as the constellation! As far as what stars the Norsemen were referring to, I would look for two stars that are close together and about the same brightness. I have two possible conclusions: first, the constellation of Canis Minor is a possibility. Another possible answer is the stars Pollux and Castor, which form the heads of the Gemini twins. I'd say the Gemini twins are the the more likely answer since they are closer in brightness to each other than the stars that form the Little Dog.