Scotland the country was (according to the usual tradition) formed by
Kenneth mac Alpin, ruler of the
Scots (relative newcomers from
Ireland), when by conquest he united his kingdom of
Dalriada with
Pictavia, the kingdom of the
Picts, in around 842. See
Kings of Dal Riada for the rulers before him.
He did so because he claimed the Pictish throne by right of succession: his father Alpin (d. c. 837) was the son of Eochaid IV "the Venomous" of Dalriada and of the heiress of the Picts. However, see under Kenneth mac Alpin for a much more detailed discussion of the truth and politics of all this.
The Gaelic name for it was Alba, the Latin name Scotia. The royal title was ethnic rather than territorial: "King of Scots" (rex Scotorum).
Here are the early rulers up the point at which the previous write-up takes up the story. The kingship alternated, with considerable violence between the senior and junior lines of descent from Kenneth MacAlpin: I'll mark them (S) and (J) so that the "son of" lines can be followed back more easily.
The earlier dates are not known to the exact year; you may see them a year or two different in other sources, into the 900s.
Kenneth I (MacAlpin) 842-858 (king of Scots c.840)
Donald I 858-862 brother
Constantine I 862-876 (S) son of Kenneth I; killed in battle
Aedh (or Aed) 876-878 (J) son of Kenneth I; killed in battle
Eochaid 878-889 grandson of Kenneth I by a middle child
and Giric 878-889 (I don't know what happened here)
Donald II 889-900 (S) son of Constantine I; killed in battle
Constantine II 900-943 (J) son of Aedh; abdicated
Malcolm I 943-954 (S) son of Donald II; killed in battle
Indulf 954-962 (J) son of Constantine II; abdicated
Dhubh (or Duf) 962-966 (S) son of Malcolm I; killed in battle
Cuilean (or Culén) 966-971 (J) son of Indulf
Kenneth II 971-995 (S) brother of Dhubh
Constantine III 995-997 (J) son of Cuilean; end of (J) line
Kenneth III 997-1005 (S) son of Dhubh; killed in battle
Malcolm II 1005-1034 (S) son of Kenneth II, and cousin of Kenneth III
then as listed above
Anyone not listed as killed in battle or abdicated was murdered or just plain killed: as far as I can tell the first king to die peacefully during his reign was Edgar in 1107.
Duncan I and Macbeth his murderer were cousins, both sons of two daughters of Malcolm II. Macbeth was married to Gruoch, granddaughter of Kenneth III. By a previous marriage (to Gillacomgan, Mormaer of Moray), she had a son Lulach. Contrary to Shakespeare, Macbeth was not succeeded by Malcolm, but by his stepson Lulach, who held out for a year before being killed in battle (he was a grown man with two children) the following year.
Malcolm III Canmore and Donald Bane (Shakespeare's Donalbain) were brothers. Duncan II, Edgar, Alexander I, and David I were all sons of Malcolm III. The last of these was succeeded by his grandson Malcolm IV, and Malcolm by his brother William I. Thereafter the succession is father to son except as noted:
Alexander III's daughter was married to King Eric II of Norway; she died before her father, leaving an infant Margaret, the "Maid of Norway", who on Alexander's death was recalled to the throne of Scotland, but she died soon after.
Only distant descendants of David I were left to contest the crown: Edward I of England adjudged in favour of the claim of John Balliol, who swore fealty to him at Scone; but when Balliol tried to assert more independence, Edward marched against him, and compelled him to abdicate. After a long interregnum, Robert the Bruce, another distant cousin, finally took the crown. During the reign of his son David II, Edward Balliol, son of John, raised rebellion several times and was the crowned king of Scotland for three months in 1332.
David II Bruce had no children; his sister Marjorie was married to Walter, sixth hereditary High Steward of Scotland. Their son Robert Stewart was the first king of the Stewart dynasty.
James I was a captive in England for most of his reign, from 1406 till 1424. James IV was killed in battle at Flodden Field: his queen was Margaret, daughter of Henry VII of England. Mary abdicated in 1567 and was kept captive in England until her execution in 1587. James VI succeeded Elizabeth I on the English throne in 1603, because of his descent from that Margaret of England, the Tudor line having been exhausted.
Scotland and England were separate kingdoms until 1707, when Great Britain was formally created by the Act of Union. Although England was a republic between 1649 and 1660, Charles II tried to assert his claim as king of Scotland immediately after the execution of his father: he was crowned at Scone in 1651, but had to flee.
On the naming of modern rulers: I believe that around 1900 it was decided that future rulers of the United Kingdom would bear the higher of their English and Scottish regnal numbers. So James VI of Scotland became James I of England, and James II of England was technically James VII of Scotland, before the union of the crowns, but the next king James will be called simply James VIII, and the next Robert will be Robert IV though England has never had a Robert, and the next Henry will be Henry IX.