When you reach a certain level you can go to the "future" and meet the future kings/queens and they give 2 type of quest, one of them is the hero quest and the other is the holy swords and Evil sowrds quest.
So im going to do a guid on the hero quest because its easy compared to the swords quest. ( recommended for beginner to start with this one first)
Ok when your fame is high enought you can take the quest. Go into the portal behind these npc's...
Once inside talk to this npc (D.Guide)...
After that go back through the portal and talk to this npc (D.Heroend)...
Don't take all quest items just yet, it will just waste your inventory space.
I suggest you take claire's poster (option 5), and arus's poster (option 4).
Ok now to find Claire
After u find her she will thank you for the information on the black hair knight, females only will have to do a quest at this part. And she will request another quest of you, both male and female will have take this quest.
Choose option 3 after the quest is completed (females), or just talk to her again and choose option 3 (males). As for the seconde quest you can do it or just drop it.
Now for arus's signature.
Arus is the guy that females had to talk to earlier. Well for guys you just have to go to the bar and find a guy sitting at in the right corner.
Ok now talk to him and he won't sign your poster, the reason... " he want 2 be alone for awhile to think about something." For a chick? Lets help him solve his problem.
Choose option 3 (request a quest from him), then choose option 2, then choose option 1 (fortune teller quest).
After you accept it your inventory will have a piece of gold in it, (never ever try to drop it).
Ok now go to madelian and find this shop you will find a beatiful npc inside.
Talk to her and she will do arus's fortune telling. After the fortune telling check your inventory, you will notice that the gold quest item is gone and now you have a letter quest item. Head back to arus and tell him about his fortune.
Choose option 4 to complete the fortune telling quest for fame and money. Talk to him again and choose option 2 to get his signature.
After that go back to this npc where you got the posters and give him the signed posters for the reward, each signed poster is worth a whopping 900 fame and 12k of exp so go for it ><!
(Special note, this is just the begging of the quest as there are other posters to get signed, so go out there and find them!)
Courtesy of oSeNo
For Baldea signature, i suggest everyone to do it when they are at least level 40+ or accompany by some high level friends. This is because she is inside the clements mine first floor where all the other scorpy the general is around. If you are lucky, those level 60 and 61 scorpy the general might wonder off to somewhere. Otherwise, you are a dead meat. (she is the green elf)
For Duran's signature, i suppose this one is the toughest among all. FIrst you have to talk to the pink/red hair girl in the tavern in Elim. When you ask about where is duran, she will tell you to find the first knight or something like that. then you will have to go to Lime to finish the quest from Slay (which is find him a gold piece, and has to be part of the militia i believe). After that, go to Adel, and talk to the driver and choose the option that says "Yes". You will transport to some place where the first knight - Leona is. Talk to the NPC, and choose option 2. After that, get ready for yourself. Fullfilled your HP and AP, and if you bring a cleric/ you are a cleric then ask/use the package. Done? Fight the Bale, it's lv.53 with steel element. Defeat the bale and you will speak with him, and he'll tell you something. Finish it off, then you will get the signature from him. (high level required. suggest at least 50+, if you are knight, then maybe you can do it sooner, but not guarantee)