My friend Trahaearn and I just completed the Fellowship Quests and got my NPC. Here's how to do it.
First, talk to Luto Mewrilah to get the quest in Upper Jeuno. She will give you a list, this let's you chose the race and name of your NPC. Make your selection and talk to the people of Jeuno to start tracking your NPC down. My friend and I talked to a Mithra outside of the Merry Minstrel in Lower Jeuno, but Aceofwilds has said that he talked with Red Ghost in Port Jeuno. Either way, the person you talk to will ask you what kind of hair your NPC has, your answer determins their hairstyle.
Next, go to Bheem in Upper Jeuno (near the gate), he will ask you if the NPCs hair is his favorite color or not. This determines the hair color.
Return to Luto for your Silver Ingot and quest completion. Zone out and talk to her again for the next quest. Go talk to Bheem again after the CS at Luto. Next head G-8 entrance of Eldemie Necropolis and find a ??? inside. Clicking on it will spawn a Skeleton NM, defeat it with the aid of your NPC and speak to the NPC. Head back to Nuto in Jeuno to complete this quest. Once again, zone out and back in to get the next and final quest.
After speaking to Luto again, head to Port San d'Oria and find Portaure and speak to him for a CS. Now head to Fort Ghelsba for a lvl 40 capped BCNM at the Hut Door.
In the BCNM you will be solo fighting a Dragon. After bringing it to half health, your NPC buddy will show up and help you finish it off. After another CS, return to Luto one final time to get your Signal Pearl and the ability to summon your NPC friend.
Quote from: Gattsu
Is there any way to determine what job class your NPC might be?
Eldemie Necropolis and find a ??? inside. Clicking on it will spawn a Skeleton NM, defeat it with the aid of your NPC and speak to the NPC.