The Oxford English Dictionary says:
It was not until the 17th cent. that Your Majesty entirely superseded the other customary forms of address to the sovereign in English. Henry VIII and Queen Elizabeth I were often addressed as ‘Your Grace’ and ‘Your Highness’, and the latter alternates with ‘Your Majesty’ in the dedication of the Bible of 1611 to James I.
The earliest English quotation in the OED is from the late 14th century, but that is not a direct address (it says "his lordschipe and mageste"). The earliest one given that addresses the sovereign is from about 1425: "Displese it nat, nor to ȝour worþines, In presence of ȝour maieste Þat I schal seyn."
(Editing to add a bit more about why the term came into usage:)
http://www.heraldica.org/topics/royalty/highness.htm discusses "inflation in titles," and says:
From the 12th to the 15th c., the kings of France, England, Castile, Aragon, Portugal used the style Highness (Fr: Altesse, Ger: Hoheit, It: Altezza, Sp: Alteza) as their prerogative, though not to the exclusion of other styles (French kings were also called Excellence until Louis XI in the 15th c.). Same went for the Emperor.
When Charles V became emperor (1519), he decided that Highness was not enough for his elevated status, and started using Majesty. Immediately, his rival François I of France insisted on the same: the treaty of Cambrai (1520) only styles the Emperor as Majesty, but the treaty of Crépy styles François as Royal Majesty and Charles as Imperial Majesty, and the Câteau-Cambrésis treaty (1559) goes further with Most-Christian and Royal Majesty. Henry VIII of England followed suit, but in England the terms Majesty, Grace and Highness were all in use until the end of James I, when Majesty became exclusive.
However, the quotations in the OED (and also in the Middle English Dictionary) do show the usage appearing well before this. It is not always clear out of context to whom "your majesty" is being directed, though. (See for yourself in section 2.a. of the MED page.)