It's the eternal question... who exactly was Link looking for when he began his personal journey into the Lost Woods in the prologue to Majora's Mask? Many say it's Navi, others say it's the Skullkid, and a few dim bulbs say he was looking for Saria or Epona. But let's settle this issue once and for all, right here & now.
Game begins with a black screen and in white letters the prologue above is told, word for word. As soon as the last paragraph fades to black, a fairy swish sound is heard. The screen lightens, and there are trees and fog, and then shows Link riding Epona slowly through the Lost Woods. He looks somber and half-asleep. Tatl and Tael appear, look at Link, then fly off, making a fairy swish sound. Link then looks around the area, as if he had never been this far into the Lost Woods before, or looking for the source of the sound just made.
T&T scare Epona, she rears back, throwing Link to the ground and he hits his head. Skullkid appears, T&T fly up to him, and he then congratulates him. He looks over at Link, and for a moment, seems to recognize him. He quickly dismisses it and walks over to him, then steals his ocarina. Skullkid plays a few notes then laughs, as T&T argue over it. Link wakes up, shakes his head, then stands up to face Skullkid.
This startles him and the fairies, and he quickly hides the ocarina behind his back. Link then tries to grab Skullkid, but he dodges and hops onto Epona. They start to take off, but Link hangs on to Skullkid's foot and gets dragged along. They go deep into the forest. At a sudden turn Link looses his grip and tumbles to the ground, and Skullkid, Epona, and the two fairies gallop off into a forest tree cave thing. You are able to play shortly after.
Navi - Link's fairy guide in OoT. She gave him lots of helpful advice on monsters, areas, etc. Appointed by the Great Deku Tree to guide Link, and helped convince Princess Zelda that Link was the boy from her prophetic dream.
Skullkid - An imp/creature that lives in the Lost Woods. Became friends with Link in OoT when, as a child, played Saria's Song to him. Link also was able to sell the Skullkid a Skull Mask, although he got gypped by 10 rupees or so. When Link returns to the Lost Woods as an adult, he finds Skullkid again although he and the other skullkids shoot poison darts at Link.
Saria - Link's childhood friend. She stood up for him when the rest of the Kokiri clan picked on him because he didn't have a fairy. She later awakened as the Sage of the Forest and guardian of the Forest Temple. While still friends, she could no longer be with Link because of her role as Sage.
Epona - Link's horse companion. Epona was born and raised on the Lon Lon Ranch, and is the apple of Malon's eye. Link became friends with Epona (and Malon) after learning Epona's Song. As an adult, Link was able to tame Epona and remind her of their friendship by playing said song. Epona is very fast.
...Time to narrow down the search...
Link *obviously* isn't looking for Epona, because he's riding her in the opening scene! Hello!! A 'prologue' is an introduction, something that happened *before* the story or game takes place. So even though Epona does get stolen by the Skullkid in the opening sequence, Link didn't originally go into the Lost Woods to find her. Not to mention that the Prologue states that Link was searching for a friend that he parted ways with when he fulfilled his destiny. Link never parted ways with Epona in OoT.
People think it's Saria because at the end of the game, they play Saria's Song. Link is leaving to go back into the Lost Woods, and in case you forgot, Saria's Song is also the Lost Woods theme. It is also the song which Link played for the Skullkid in OoT. The song fits because it is light and cheery, perfect for the ending. Not because it secretly means he was looking for Saria. Although Saria could be considered a "beloved and invaluable" friend, there is hardly no evidence that Link went into the Lost Woods to find her. For one, Saria is no longer staying in Kokiri Forest or the Forest Temple. During the end of game credits, Saria is seen with the other Sages. All together they fly/transport themselves to the big group party in Hyrule Field, she flies around a depressed Mido a few times, then she and the others fly off into the distance. Together. It is assumed that she is still with the other Sages, probably watching over Hyrule and the Sacred Realm, maybe from the Light Temple. When Link awakened one of the Sages in OoT, he was transported to the Chamber of Sages inside the Light Temple where the Sages gathered. Either way, if Saria *had* returned to "normal life" after Ganon was defeated, she would go back to Kokiri Forest, or stay in the Forest Temple. Not lost somewhere deep inside the Lost Woods. And to stick with the Prologue, Link did not part ways with Saria when he fulfilled his destiny. True, he parted ways with Saria, since they could no longer be together, but that was waaay back in the middle of the game. Not at the end, where he becomes a Legend.
Now! On to the main showdown!
A few stubborn people believe Skullkid is the friend Link was looking for in the Prologue. They think this because the Skullkid recognizes Link as the fairy-boy he met in OoT, for they met in the Lost Woods. But here are my reasons why Link was NOT looking for the Skullkid in Majora's Mask.
1) I would not say that Link and the Skullkid were good friends in OoT. They were more like... friendly acquaintances; someone who when you pass them by nod your head and say "Hey". Not someone whom you would confide with your deepest troubles.
2) The Prologue clearly states that Link is looking for a "Beloved and invaluable friend". Skullkid was neither beloved nor invaluable, since everything that had to do with him in OoT was a side-quest. You didn't need to talk to Skullkid in order to defeat Ganondorf, collect a Medallion, or anything. A heartpiece and selling a mask was as deep as their friendship got. Skullkid knew nothing of the horrors Link experienced, the loss and pain he felt, or the intense pressure he was under for trying to save Hyrule.
3) The Prologue also states that Link "parted ways" with the beloved friend when he "fulfilled his destiny and took his place among legends". It is common sense that this takes place at the end of the game, when he defeats Ganon and saves Hyrule. It was Link's destiny to save Hyrule from Ganon, and that only happened at the very end of the game. However, Link does not see the Skullkid at the end of the game. The Skullkid does not come to aid Link with his destiny, nor does Link ask for his help. There is no further interaction between them, especially since it appears that the Skullkid hates Link in his adult form. Therefore, it is silly to think that Link would travel to the Lost Woods in order to search out a 'friend' whom he was hardly close with.
Navi stayed by Link's side from the very beginning of the quest to the very end. Only once did Navi not aid Link, and that was because Ganondorf's dark magic was too much for her and she couldn't get close to him. But she returned when Ganondorf was defeated, and stayed to help Link for his final battle against Ganon. Because Navi was always with Link on his journeys, they grew a special bond. A kind of bond that only appears with those who share heavy burdens together, and go through many trials together.
Link was looking for a "beloved and invaluable friend". All the information that Navi provided willingly for him in OoT would certainly be invaluable to him, especially since he had never journeyed outside of Kokiri Forest before and many things were new to him. The beloved part can come from the fact that they were together and helping each other for 99% of the game. Everything Link had known and loved was changing. The Great Deku Tree died, his friends were gone, he was fighting monsters non-stop, the Princess had disappeared, and a power-hungry psycho from the Desert was ravaging the land. The only thing that stayed constant in Link's life during this adventure was Navi. Navi was always there for him. In the face of danger or for a peaceful moment's rest, she never abandoned him. That sure sounds like a good friend to me.
The Prologue states that Link "parted ways" with his beloved friend when he "fulfilled his destiny and took his place among legends". When the battle was over and Link and Zelda said their tearful goodbye, Link was returned to the Master Sword room in the Temple of Time as a child. It was then that Navi flew up, flew up towards the only window and disappeared. Alone Link left and went to visit Zelda, at that was the end of Ocarina of Time.
Link does not enter the Lost Woods to find Zelda, because 1) Why the hell would she be in the Lost Woods, and 2) When Link retrieves his stolen ocarina from the Skullkid in Majora's Mask, he gets a vision from the Princess, and it is clear that he said goodbye to her before he left on his journey.
So that leaves only one Beloved and Invaluable friend, Navi. Want more evidence? When the Prologue is finished in the opening scene, you hear a fairy swish sound. Some say that this is Tatl and Tael's doing, but the sound is heard WHILE the screen is still black, before you even see that Link is in the Lost Woods. Why the hell would they play a fairy swish sound after a prologue and before the hero is seen if there's not a connection?! It doesn't make literary sense.
In the Legend of Zelda manga by Akira Himekawa, she depicts Link as searching for Navi in the beginning of Majora's Mask.
Still not enough? Then chew on this. Straight from the source, yo! According to the Collector's Edition Strategy Guide by Nintendo, they say that Link was looking for Navi. Boo-yah.
Link was looking for Navi in the beginning of Majora's Mask. End of story. But the game leaves you hanging at the end, because even though he retrieves his stolen ocarina and horse, and saves Termina from certain doom, he didn't find Navi. That is what has so many people irked, and has them trying to convince themselves that the world is flat. Erm, I mean, that Link was looking for Skullkid. '>_>
People, you should know by now that not everything in the Legend of Zelda series is tied together in a nice little package! There are many plot holes, there are many questions, and there are many missing stories. That is what makes this series so interesting! So what if Link didn't find Navi at the end of Majora's Mask and they didn't live happily ever after. It doesn't mean that Link didn't continue to search for Navi, or that she eventually found her way back to him. Who knows! Until they make a game for it, or make references to it in a future game, there's no telling what happened. But we do know whom he was searching for, and that is good enough for now.