The phrase is derived from John Hobhouse stating His Majesty's Loyal Opposition in 1826 in a debate in the British parliament.
[1][2] It is intended to illustrate that Members of Parliament in a country's legislature may oppose the policies of the incumbent government—typically comprising parliamentarians from the party with the most seats in the elected legislative chamber—while maintaining deference to the higher authority of the state and the larger framework within which democracy operates.
[2] As a consequence of this parliamentary evolution, the sovereign's right to the throne became more concrete, seeing the opposition scrutinise government legislation and policies, rather than engage in disputes between competing candidates for the Crown, each supported by different religious and economic groups.
Further, the acceptance of such a thing as a loyal opposition in Parliament factored into the development of a rigid party system in the United Kingdom; the separation of Members of Parliament's loyalty to the Crown from their opposition to the sovereign's ministers eliminated the idea that there could only be one "King's Party" and that to oppose it would be disloyal or even treasonous.
[1] Also, in federal countries, such as Canada and Australia, the phrase His Majesty's Loyal Opposition is also employed in provincial or state legislatures, in the same fashion as in other parliaments.