Malcolm's attempt to retake the throne didn't immediately have that effect, of course. After Macbeth's death, his followers immediately put a man named Lulach mac Gille Comgaín, a grandson of a king from the former dynasty, on the throne of Alba. He did not reign long, only about a year, and then he was killed and Malcolm came to the throne as Malcolm III. Some sources suggest that he attempted to set up talks with King Edward of England, who would eventually become known as Saint Edward the Confessor, in order to marry Edward's kinswoman Margaret (more of her in a moment). But since he very soon afterward invaded Northumbria, either he never really did so or the talks did not go well at all. Instead he married a woman named Ingibjörg Finnsdóttir, who seems to have been the widow of Thorfinn Sigurdsson, better known as Thorfinn the Mighty, who was the Earl of Orkney.
Now, Thorfinn Sigurdsson had been an unusually powerful and effective Earl of Orkney, ruling for seventy-five years, and according to the Orkneyinga Saga, he had earlier been engaged in a war with the "King of the Scots":
Then Karl Houndson took the rule over Scotland; he thought he ought to own Caithness too, like the former Scot-kings; and he would have scatt from that part of the realm as from other places, but earl Thorfinn thought he had not too great a heritage after his mother’s father, though he had Caithness. He said that realm had been given to him, and he would pay no scatt for it; now out of this arose a mighty feud, and each harried the other’s realm.
'Scatt' is an archaic word, derived from Norse skattr, for tribute. Now, we know of no King of Scotland whose name was Karl Hundason; and, indeed, it would be an odd name for any king to have. The Saga is not particularly reliable as a historical source, so it could simply be made up. If it does refer to real events, 'Karl Hundason' seems to be an insult-name: Churl, son of a dog. The whole story is consistent with the possibility that it really describes, in grandiose terms, a dispute between Thorfinn and the Mormaer or Steward of Moray -- and as Macbeth had been Mormaer of Moray, it is very possible that if there really was a Karl Hundason, Karl Hundason was actually Macbeth. In any case, Thorfinn managed to hold off 'Karl' with no real problem, and thus established Orkney for a time as perhaps the major power of North Scotland.
So it's perhaps unsurprising that Malcolm took the trouble to marry Ingibjörg in order to consolidate his power and influence. In any case, Malcolm and Ingibjörg had a son, Donnchad, who eventually became King Duncan II, and throughout Malcolm's reign relations with Orkney seem to have been very good. Ingibjörg eventually died, although we don't know exactly when.
In the meantime things were happening down south. King Edward of England died childless in 1066. His closest living relative was Edward the Exile, who received that epithet because his family had been exiled to Hungary by King Cnute after Cnute had invaded and taken over England. (King Edward's own kingdom had been a brief restoration after Cnute's death and the dissolution of his North Sea Empire.) On discovering that he was still alive, Edward the Confessor called Edward the Exile back to England to name as his successor. Edward the Exile had a wife, named Agatha, a son, named Edgar, and two daughters, named Margaret and Cristina, and they returned with him.
So far so good, but as it happens Edward the Exile died in 1057, two days after having arrived back in England. Nobody knows why; it's one of those deaths that was suspiciously convenient for a sufficiently large number of people that it's almost certain he was murdered, although nobody knows by whom. This death would leave King Edward's succession in dispute: Edward the Exile's son Edgar was proclaimed king after King Edward's death in 1066, but both Harold, Earl of Wessex, and William, Duke of Normandy, claimed that they were the legitimate heir to the throne, and, in fact, William of Normandy invaded. The Witenagemot or High Council of England recognized that Edgar was in no position to fight this war with the weak backing he had, so they named Harold, Earl of Wessex, as Edward's heir. Harold, however, was killed at the Battle of Hastings, and so the Witenagemot elected Edgar king again. But he was never crowned. William mowed down any opposition to him, and the Witenagemot had Edgar surrender to him at Berkhamstead.
In 1068 Edgar fled with his mother and sisters to Scotland. Malcolm III, now widowed, saw an opportunity, and agreed to support Edgar in his attempt to regain the throne from William. By 1070 he had married Margaret, Edgar's sister. Malcolm invaded Northumbria a few times, but nothing ever came of them. Malcolm and Margaret had eight children, and notably they all have English names: Edward, Edmund, Ethelred, Edgar, Alexander, David, Edith (or Matilda), and Mary. Edward died early; Edgar, Alexander, and David would each become King of Scotland; Edmund became an important Abbot; Matilda married King Henry I of England, and Mary married Count Eustace of Boulogne, who went with his brothers Godfrey and Baldwin on the First Crusade, where Godfrey became ruler of Jerusalem and Baldwin, Count of Edessa, and later King of Jerusalem. That's an entirely different set of stories.
Margaret of Scotland was famously pious: she attended church regularly, went out of her way to do good works for the poor, and was generally well-loved. She became known early on as an exemplary case of the just ruler, and was held up as a model for all royalty to follow; she was canonized in 1250. Saint Margaret of Scotland died on November 16 in 1093; and today is her feast day in the Catholic calendar.
I really do think this would make a more interesting television series than most things you find on television. Who doesn't like Vikings, Scottish kings, Anglo-Saxon political bickering, and Norman Invasions, all rolled into one big story?