The norse kingdoms would be like the kievan rus, as Ville Niemi said in another answer - natives with a nobility that descended from the norse. Trade in the Atlantic would begin much earlier but would be limited due to shipping costs. Norse boats were small and had to hop from Canada to Greenland and then to Iceland so american products would be quite expensive. Which products would be traded?
From America to Europe: Tobacco, furs, ivory[from the polar fauna],whale oil, slaves, gold/silver. It would be more efficient to send the cigars then the dried tobacco leaves, the coats and capes then the raw furs, the many useful things made of ivory then the walrus and narwal tusks, and jewelry then raw gold and silver.
From Europe to America: Iron tools and weapows, horses, cloth, silk and spices (from the silk road).
The main trade hubs would be in England and, due to that, England would prosper but would still probably be a saxon christian England instead of a norse pagan England. Also, Novgorod and Denmark would prosper too, as the silk road would branch north. That would mean that when the crusaders destroy Constantinople during the fourth crusade the russians won't go bankrupt and will have better chances against the mongols. So, in europe, England, Denmark and Novgorod will be more powerful then they were. That could mean that the english might be able to conquer and keep France, the danes could keep the swedes under the danish crown and some kind of Russia would form earlier, maybe as a giant merchant republic instead of an autocratic monarchy.
The demand for better ships to do this trade would bring about big ships like the north european cogs. But true ocean ships would still take a long time to appear due to the lack of compass and good astronomical instruments. They may have galleons 2 century earlier but won't dare to do a direct cross due to lack of navigation tools, instead, they will keep doing the island hopping from Canada to England.
Also, religion: Christian (and muslim) missionaries would find their way to America much earlier. Christianity and Islam was useful to tribal societies because it gave them a worldview that favored monarchical centralization, helping the tribal petty kings become feudal kings. So, the american norses (and the native americans that interacted with them) would probably adopt christanity or islam. But there is an alternative...
"Pagan" religions began as tribal, limited to what the tribe knew about the world. As the tribe's horizons expands, the pagan religion becomes more and more universal, as the priests see the similarities between the varius spirits worshipped by the other tribes. The final result is something similar to neoplatonism, taoism or the egyptian religion: a complex religion, with a deep, developed, worldview capable of orienting it's followers in all phenomena in the world. The ancient greek religion evolved like that, from the greek dark ages to the Plato, the african religions are evolving like that today as result of the african diaspora in America, that mixed the african tribes, the american tribes and the european magical systems. So, the norses, in contact with christianity and islam, with the slavic tribes and the american tribes, could develop a new great world religion.