5 RINGS, it depends very much on the aircraft you are operating and the equipment that's installed. There are two sides to the PRNAV (also known as RNP 1) process.
1. Gaining the Certificate of Required Navigation Performance by going through the paper chase to demonstrate that your equipment fit and its modification status meets the necessary standards. The 1 nautical mile guaranteed long term performance accuracy involves not only the Inertial Nav, GPS, FMS and DME, but also includes other systems such as the navigation displays and consideration of the effects of various system failures.
2. Getting your operations manual procedures certified.
If your fleet is Boeing or Airbus for example, much of this work is already done for you; you have only to do the drafting work for the submissions. For other less well supported aircraft (Fokkers for example) you may have to do a lot of searching and/or pay some pretty stiff 'certification' fees.
Then there's the vexing question of knowing what RNP procedures are actually in use and where. Although Eurocontrol have all the info and led the way, it isn't just Europe that imposes RNP rules. Think about Australia for example...
Feel free to PM me for more detailed information.