Let's work back...
1) The Commonwealth of England, Scotland, and Ireland lasts. Boom!
2) Royalists win ECW or, better, more delicate royal politics mean it's never fought (Henry Stuart lives?) and the royal house is able to gradually continue consolidating its power.
The Stewarts were pretty union-mad until the idea became associated with Cromwell and, at the same time, they realised the value of playing one kingdom off against the other. Remove those factors and their long-term ambition for Union - which circa 1604 was going nowhere in England, although as Thande points out we were more keen - may come to pass.
3) England stays Presbyterian (Edward VI lives): if that happens, a *union of crowns at about the same time had a much better shot of leading to a full political union.
4) Speaking of Edward VI: I don't really know how to arrange it, but perhaps some continental butterfly to the detriment of France means Somerset can win the Rough Wooing, enforce a union of crowns, and ensure that whichever Protestant discipline England adopts, so does Scotland. This one's go pedigree: John Knox, who was at the time a senior figure in the Presbyterian-inclined CoE, lamented the missed opportunity in his history of the Scottish Reformation.
5) Skipping over a bunch of stuff where some opportunities probably exist but broadly speaking England is stuff in France and remembers what happened the last time...
Edward I could probably have subdued Scotland if Robert the Bruce had just plain drowned on his way out of Ireland. He may have been an evil horrible bastard, but his military skill and sheer bloody-minded ruthlessness succeeded where the rest had failed. If not him and his faction, who? The English had prevented the return of Balliol and learned their lesson about coercion verses conciliation, so although they didn't really control anything beyond the Forth, they may succeed in getting their sovereignty recognised as in Ireland.
Surer and better, however, to have the Maid of Norway live and Scotland peacefully enter into Angevindom like everyone planned for. The Scottish and English elites would not become as intertwined and similar as they were in 1286 until, oh, a bittie after 1832?, so if this had happened and lasted one would think that political union would follow naturally in a couple of centuries.
I honestly don't know whether any of the subsequent Balliol-based attempts to set up an English client regime had much chance, but given that the Bruce line were in exile at one point, you'd think so. No Hundred Years War = English southern Lowlands and a Scottish vassal?
6) England's earliest intervention in Scotland was a big success, even if Shakespeare was exagerrating.

If the Earl of Northumberland, acting largely by himself, could depose the king of Alba, one would think that Saxon England - relatively unbothered by what goes on in France, and quite possibly more and for longer conscious of itself within a Scandinavian world with Scandinavian threats - would keep a damn close eye on the Canmore line he had put in its place.
(As a matter of fact, despite the best efforts of the monks or Melrose to expunge this event from history, Malcolm
did do some sort of personal homage to William the Bastard, though it was a much less formal relationship than what Edward I was talking about. But William was provoked to that by our support for the Last of the English and, when the threat of Saxon resurgence with the support of outside powers was gone, seems to have largely forgotten us.)
7) As mentioned, something sub-Roman. Rheged, the strongest British kingdom which at one point was on the point of defeating Northumbria, extended into modern Scotland; all the kingdoms between the Antonine and Hadriine walls clearly considered themselves Romano-Britons. If the Saxons never turn up/are confined to the southeast of England as subjects of the High King, everything up to the Forth-Clyde line looks more to the British world than to the Pictish and Gaelic north.