Speaking to Naja after starting the quest gives you the option to have Naja review each of the three objectives (Chariots/Beastkings/Odin) with you. After you complete one of the three objectives, she no longer offers it as an option for review. Until one category is complete, however, she does not acknowledge any sort of progress. You do not need to currently have the title (or titles) in order for Naja to be aware that you have defeated an NM.
Once you have defeated all eight NMs, return to and speak with Naja Salaheem.
If you had already beaten all 8 NMs before flagging the quest, simply speak to Naja Salaheem immediately after receiving your objectives to complete the quest.
When replaying the cutscenes for this quest at Tsih Kolgimih, you are given the option to choose which weapon is turned in, or to "randomly fork one over."