What is an Inertial Navigation System? How does it work?
Inertial Navigation Systems, unlike other navigation systems, do not depend on external (radio) measurements. Instead an INS keeps track of its position by accurately measuring acceleration (accelerometers) and rotation (gyroscopes). It therefore works in remote areas where there are no ground based navaids available. 

Initially, the INS gets its position from pilot input at the gate, or in more recent systems from GPS, sometimes even during flight. By measuring all the accelerations and rotations and integrating them into speed and direction the position is tracked. In doing this, the INS has to correct for the rotation of the earth and the related Coriolis force. 

Due to small inaccuracies in the measurements the velocity error and, with that, the position errors grow over time. 

Wikipedia has quite a detailed article about the history and working of the INS.

While raw INS position has mainly been replaced by GPS measurements on oceanic flights, the system is not being phased out. GPS is a sensitive systems and by crosschecking it with INS, errors can be detected in both systems. It is often used as a backup to GPS. 

Integrated GPS / INS systems provide better systems integrity and allow the navigation system to coast through short GPS outages with high accuracies. In addition to that, the (laser) gyroscopes of the INS are often used to provide data to the digital artificial horizon displays in the cockpit and to the auto flight systems. In this case the term Inertial Reference Unit (IRU) is used, which acts as a basis for the INS.