Question: In our everyday experience termperature is due to the motion of atoms, molecules, etc. A neutron star, where protons and electrons are fused together to form neutrons, is nothing but a huge nucleus made up of neutrons. So, how does the concept of temperature arise?

Answer: 
First, strictly speaking a neutron star is not a nucleus since it is bound together by gravity rather than the strong force.

Measuring a surface temperature for any star is deceptively simple. All that is needed is a spectrum, which gives the luminous flux (or similar quantity) as a function of photon wavelength. There will be a broad thermal peak somewhere in the spectrum, whose peak wavelength can be converted to a temperature using [Wien's displacement law](http://en.wikipedia.org/wiki/Wien%27s_displacement_law):

$$T=\frac{b}{\lambda\_{\rm max}}$$

with $b\sim2.9\times10^{-3}\rm mK^{-1}$. Neutron stars peak in the x-ray, and picking a wavelength of $1\;\rm nm$ (roughly in the middle of the logarithmic x-ray spectrum) gives a temperature of about $3$ million $\rm K$, which is in the ballpark of what is typically quoted for a neutron star.

More broadly than the motion of atoms or molecules, you can think of temperature as a measurement of the internal (not bulk) kinetic energy of a collection of particles, and energy is trivially related to temperature via Boltzmann's constant (though to get a more carefully defined concept of temperature requires a bit more work, see e.g. any derivation of Wien's displacement law).
The answer given by Kyle refers of course only to the surface or photospheric temperature of the neutron star - the temperature of the layer from which photons can escape to reach an observer. In these outer layers the relationship between temperatures and particle motions is more-or-less consistent with the "everyday" Maxwell-Boltzmann picture referred to by the OP. 

However, the bulk of a neutron star is *much* hotter than this, probably by a factor of 100 or so. In thermal terms, a neutron star consists of an isothermal core (the vast bulk of the star) surrounded by a very thin (maybe a few metres) insulating blanket, across which there is a big temperature drop.

Inside the neutron star there is a shell of material containing neutron-rich nuclei and degenerate electrons, where the traditional concept of temperature (at least as applied to the nuclei) still has some merit in terms of the kinetic energies of the nuclei. In the inner regions, containing $>95$ percent of the mass, there are mainly neutrons with a small (1%-ish) fraction of protons and electrons. These are all degenerate gases.

In degenerate gases, the concept of temperature is a bit more slippery. The neutrons occupy energy states according to Fermi-Dirac statistics in the low temperature/high density limit; *the kinetic energy of the neutrons becomes almost independent of temperature* and entirely dependent on density. As a consequence the gas pressure is independent of temperature and these degenerate gases contain very little thermal energy, even when they are at extremely high temperatures.

This is why neutron stars cool extremely rapidly - their degenerate interiors contain *much* less thermal energy than a non-degenerate gas at similar temperatures.