What we know so far about these NM and HNMs, which we've dubbed VNM (Voidwalker Notorious Monsters):
You can start this easily enough by talking to Assai Nybaem in Ru'Lude Gardens, to the right of the signet NPC (facing Upper Jeuno). Listen to him ramble on about voidwalkers and abysseans and all that hooplah, and then get to the point and buy a "Clear Abyssite" key item from him for 1,000 gil.
Go into one of the zones (list provided below) and rest. Easy enough. You'll get a message telling you if there are any NMs nearby, and how many yalms away they are, as well as in which direction. Get close enough to one and rest, and it will come out to play.
So far it seems like they work in Tiers, similar to ZNM. There 5 paths in total it seems, all ending with the Wyrm Yilbegan, and consisting of 4 tiers. Tier 1/2 seem to require a random amount of kills to reach tier 3, which is the HNM. Here's a list of so far known tiers for each path:
NOTE: Paths seem to be interchangeable, you can hit Tier 1 in Jugner on Krab path, and then start popping Tier 2 Pixies in Batallia, for example.
Verthandi Path:
-Tier 4: Yilbegan (Wyrm HNM)
-Tier 3: Verthandi (Pixie HNM)
-Tier 2: Urd (Pixie NM) or Skuld (Pixie NM)
-Tier 1: Aither, Deorc, Eorthe, Puretos, Pruina, Beoht, Thunor, Lacus (8 Elemental NMs)
Zones: Rolanberry Fields/Rolanberry Fields [S]/Batallia Downs/Batallia Downs [S]/Sauromugue Champaign/Sauromugue Champaign [S]
Krabkatoa Path:
-Tier 4: Yilbegan (Wyrm HNM)
-Tier 3: Krabkatoa (Crab HNM)
-Tier 2: Capricornus (Pugil NM) or Yacumama (Devil Manta NM)
-Tier 1: Quagmire Pugil (Pugil NM) or Sunderclaw (Crab NM)
Zones: East Ronfaure/East Ronfaure [S]/Jugner Forest/Jugner Forest [S]
Blobdingnag Path:
-Tier 4: Yilbegan (Wyrm HNM)
-Tier 3: Blobdingnag (Slime HNM)
-Tier 2: Lamprey Lord (Leech NM) or Shoggoth (Hecteyes NM)
-Tier 1: Ground Guzzler (Worm NM) or Globster (Slime NM)
Zones: North Gustaberg/North Gustaberg [S]/Pashhow Marshlands/Pashhow Marshlands [S]
Orcus Path:
-Tier 4: Yilbegan (Wyrm HNM)
-Tier 3: Orcus (Antlion HNM)
-Tier 2: Jyeshtha (Scorpion NM) or Farruca Fly (Damselfly NM)
-Tier 1: Raker Bee (Bee NM) or Rummager Beetle (Beetle NM)
Zones: West Sarutabaruta/West Sarutabaruta [S]/Meriphataud Mountains/Meriphataud Mountains [S]
Lord Ruthven Path:
-Tier 4: Yilbegan (Wyrm HNM)
-Tier 3: Lord Ruthven (Vampyr HNM)
-Tier 2: Feuerunke (Toad NM) or Erebus
-Tier 1: Gjenganger (Ghost NM) or Gorehound (Hound NM)
Zones: Beaucedine Glacier/Beaucedine Glacier [S]/Xarcabard/Xarcabard [S]
Here is a chart for these VNMs, credit goes to Spira:
Any more info is appreciated. I'll try to keep this as updated as possible.