The magnetic state of Nitrogen-doped MgO, with N substituting O at concentrations between 1% and the concentrated limit, is calculated with density-functional methods. The N atoms are found to be magnetic with a moment of 1 Bohr magneton per Nitrogen atom and to interact ferromagnetically via the double exchange mechanism. The long-range magnetic order is established above a finite concentration of about 1.5% when the percolation threshold is reached. The Curie temperature increases linearly with the concentration, and is found to be about 30 K for 10% concentration. Besides the substitution of single Nitrogen atoms, also interstitial Nitrogen atoms, clusters of Nitrogen atoms and their structural relaxation on the magnetism are discussed. Possible scenarios of engineering a higher Curie temperature are analyzed, with the conclusion that an increase of the Curie temperature is difficult to achieve, requiring a particular attention to the choice of chemistry.