Telemachus travels to see Nestor—who he speaks to in Book 3—because he wants to know more information about where his father is.
Athena is the one who sends Telemachus on the journey to see Nestor, though his palace is only the first stop. He's supposed to travel to see Menelaus next. If he finds out his father is alive, he has to come home and wait for his father while Odysseus makes his way home. If he discovers that Odysseus has perished, however, he is supposed to come home, observe the proper mourning rituals, and then make his mother marry another.
Nestor, King of Pylos, is a soldier who fought in the Trojan War, much like Odysseus, Telemachus's father. Since they fought together, Telemachus believes that Nestor might have information about Odysseus's whereabouts. Nestor says that he left without hearing the fates of the others. He has heard of some men who returned home since then but he doesn't know about Odysseus.
Nestor is a wise, elderly statesman who Telemachus visits in order to try to find news of his father, Odysseus. Nestor tends to be long winded, but he also is well connected and knows what is going on. Telemachus hopes Nestor can offer him some leads as to his father's whereabouts.
As it happens, Telemachus is in luck. Nestor tells that although Odysseus had started out traveling from Troy with him and Menelaus, Odysseus returned to Troy to perform sacrifices with Agamemnon. Nestor suggest to Odysseus that he seek out Menelaus, the well-travelled Trojan king, to find out where Odysseus might have gone.
Telemachus feels under pressure to locate Odysseus because of how long his father has been missing. Penelope, his mother, is under incessant pressure to remarry, so Telemachus needs to establish whether his father is alive or dead.
Nestor, in turn, is delighted when he realizes that Athena accompanied Telemachus to visit him, disguised as Mentor. He feels honored that the goddess came to him and is pleased that she is showing the same care and concern for Telemachus as she had for his father.
Telemachus has to go see Nestor because he needs information on his father Odysseus's possible whereabouts. The Trojan War ended ten years ago, and though Nestor and Odysseus left Troy at the same time, Odysseus has not yet returned home. In fact, all the men who were expected home from the war have returned, and yet no one knows anything of Odysseus's fate.
When Telemachus arrives at Pylos, along with Athena who is disguised as Mentor, he finally meets Nestor, and he says,
"I come afar to seek some tidings of my father, royal hardy Odysseus, who once, they say, fought side by side with you and sacked the Trojan town."
He goes on to say that the fate of every other man who did not return from Troy is known, but no one is able to give them any news about Odysseus's fate or whereabouts. Nestor does not know, and so he sends his son with Telemachus to Menelaus's palace at Lacedaemon. Menelaus tells Telemachus that he heard that Odysseus was last seen on an island, "letting the big tears fall, in the hall of the nymph Calypso, who holds him there by force."
It has become more and more urgent that Telemachus find his father (or find out that he is, in fact, dead) because the suitors who wish to marry Penelope, Odysseus's wife (or widow, if he's dead), are eating them out of house and home, taking advantage of the hospitality they are due by custom until Penelope chooses a husband from among them.