What did Fiji have to do when it incorporated GPS into its aviation system?
This early ICAO document covering the introduction of GNSS (GPS) should cover the whole topic quite well. I would skip to section 3 (page 75) Information on Fiji’s Early Application of GPS Technology. But the highlights are effectively: 


  Fiji consists of 300 islands (mostly volcanic) scattered over 200 000
  square miles of ocean. Of these, only 100 are inhabited. There are
  nineteen airfields, plus seven that are privately owned, but only five
  of the nineteen have NDBs and one has VOR-DME. This means that 80 per
  cent of the area is without any form of navigation aid. There are also
  helicopter and seaplane operations. Navigation has been accomplished
  primarily through visual flight rules or dead reckoning.
  
  ...
  
  Fiji became involved in FANS and GPS in 1990/91 through briefings given by CAA Australia, and became
  convinced of the safety and cost benefits to be gained. Ad hoc trials, including long distance oceanic flights with a
  hand-held GPS receiver convinced Fiji of the potential of the GPS.
  
  ...
  
  Under a Memorandum of Co-operation (MOC) the United States FAA provided equipment and operational and
  technical support to carry out trials and demonstrations. GPS receivers were provided for installation in all domestic
  IFR aircraft. These early receivers were not certified, and special procedures were developed to ensure that all the
  information provided by the GPS was confirmed by other navigation sources.
  
  ...
  
  Some of the main features are listed here.
  
  • GPS routes had been designed to all nineteen aerodromes. The GPS route charts show GPS airways and GPS
  way-points at the intersections.
  
  • GPS checkpoints were established and surveyed on all the aerodromes, initially using a GPS receiver but
  now these have been resurveyed by an outside contractor to WGS-84.
  
  • Outside areas of VOR/DME coverage, the pilot DR is now replaced by GPS procedures.
  
  • Cloud break procedures were also designed to enable pilots to descend below cloud and make visual contact
  with the island, so that in most cases they leave a pilot at 1 000 ft above obstructions, five miles out, on the
  extended centre line. This information together with way-points were entered into the GPS receivers via data
  cards, by the CAA Fiji.
  
  • Pilots and controllers were trained and examined on the rules and procedures. Pilots also had to undergo a
  practical test before being approved and pilots may not use the GPS unless they are approved.
  
  • Based on this initial experience, the charts have been further simplified so that pilots can now select, on the
  GPS receiver, straight-in approach or cloud break, when this was needed.


This early 90's advertisement for Trimble GPS units also makes claims to being the ones that were used on these first approaches. 

According to the document Fiji basically moved everything over to GPS; en-route navigation, approaches, the whole shebang. This helped them fly safer in IFR and have way more coverage than their limited ground based beacons gave them. The US helped not only create procedures, plates and information but also equipped all Fiji based operators and airfields.