Answering the question exactly as you have asked it:
They have high-grade gyros which are initially aligned to North and then they either continue pointing North (INS) or remember where North is (IRS), and then they measure the heading angle from it. It's as simple as that.
I suspect that what you mean is "How do they find out where North is when there's no magnetic compass input to an INS/IRS?"
In this case, the answer in that they have accelerometers which are sensitive enough to measure the spin of the Earth. The way that the Earth spins, no matter where you are (except the North or South Pole), the direction of Earth spin is due East. Ninety degrees left of this is North.