We investigate the magnetic properties of Mn-doped GaN through first-principles pseudopotential calculations within the spin-density-functional approximation. We examine the nature of magnetic interactions between Mn ions, and find that the ferromagnetic coupling has a short-range nature, effective for Mn-Mn distances up to about 7 angstrom. For Mn concentrations of about 6%, we find that the ferromagnetic solution is more stable than the antiferromagnetic state, while the stability of the ferromagnetic state is weakened by electron doping. Based on the calculated exchange coupling and the percolation approach, we estimate the Curie temperature lying above room temperature. Analyzing the Mn d levels, we suggest that the d-d hybridization between Mn ions is the main reason for stabilizing the ferromagnetic state. We also find that the formation of small Mn nanoclusters consisting of a few Mn atoms is energetically favorable. Since these small clusters are stable in the ferromagetic state, offering large magnetic moments, we do not rule out a possibility that small Mn nanoclusters are responsible for the ferromagnetism observed in Mn-doped GaN.