It's the eternal question... Just who was Link looking for in the prologue of Majora's Mask? There are a number of possible candidates and theories, but as this is a Navi fansite, I'm sure you know whom my answer is for. But still, I'll discuss each of the main characters Link might have gone searching for.

But first, a detailed recap of the events in question:

  Majora's Mask Prologue Text  

In the land of Hyrule, there
echoes a legend. A legend held
dearly by the Royal Family that
tells of a boy...

A boy who,
after battling evil and saving
Hyrule, crept away from the land
that had made him a legend...

Done with the battles he once
waged across time, he embarked
on a journey. A secret and
personal journey...

A journey in search of a
beloved and invaluable friend...

A friend with whom he parted
ways when he finally fulfilled his
heroic destiny and took his place
among legends...

  The Game's Opening Sequence  

The game begins with a black screen and in a white font the prologue above is shown, 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 Link appears, riding Epona slowly through the Lost Woods. He looks somber and half-asleep. The faeries 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.

Tatl & Tael scare Epona; she rears back, throwing Link to the ground and he hits his head. Skull Kid appears, Tatl & Tael fly up to him, and he then congratulates them. 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. Skull Kid plays a few notes then laughs, as the fairies argue over playing it too. Link wakes up, shakes his head, then stands up to face Skull Kid.

This startles Skull Kid and the fairies, and he quickly hides the ocarina behind his back. Link tries to grab Skull Kid, but he dodges and hops onto Epona. They start to take off, but Link hangs on to Skull Kid'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 Skull Kid, Epona, and the two fairies gallop off into a tree/cave area. You are able to play shortly thereafter.

  The Main Candidates  

Navi - Link's fairy guide in Ocarina of Time. She gave him lots of helpful advice on monsters, areas, and people. Appointed by the Great Deku Tree to guide Link on his quest, and helped prove to Princess Zelda that Link was the boy from her prophetic dream. Navi stayed by Link's side for his entire journey, but then flew away at the end of the game.

Skull Kid - An imp that lived in the Lost Woods. Link became friends with him when Link played Saria's Song to him as a child. Link was also able to sell a Skull Mask to him, although wasn't paid the full price. As an adult Link could return to the Lost Woods, but Skull Kid wouldn't recognize him, and would shoot poison darts at him along with the other skull kids.

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 a Sage. They could still talk when Link played Saria's Song on his ocarina, however.

Epona - Link's horse companion. Epona was born and raised on the Lon Lon Ranch, though was very shy until Malon taught Link Epona's Song. As an adult, Link was able to tame Epona and remind her of their friendship by playing said song. He was able to ride the horse after that, and she will always go to him (if able) whenever he plays her song. Epona is very fast.

Now, time to ready the chopping block...

  Why it is not  Epona  

This candidate is really more of a joke suggestion, or from someone who hasn't been paying attention. Since Link is riding Epona at the beginning of the game, he clearly did not enter the Lost Woods in order to find her. I guess some people get confused because she is stolen after their encounter with Skull Kid, but it helps to remember that the prologue happened first.

  Why it is not  Saria  

Saria is a potential choice because she was a good friend of Link's, lived in the forest, and did part ways with Link during his journey in Ocarina of Time. However, finer details show that it wouldn't be her. Saria and Link "parted ways" because she was awakened as the Forest Sage, and later joined the other sages in the Light Temple. This happened early to mid-way through Link's journey, so that immediately cancels out the prologue's text that Link and the friend split ways when he "fulfilled his heroic destiny," which would be at the end of the game.

In addition, during the ending credits of OoT, Saria is shown with the other Sages and together they fly off into the distance. If the Sages did return to normal life after the OoT events, she would return to her home in the Koriri Forest village, or maybe to the Forest Temple. It seems bizarre and illogical to me that, if the prologue was referencing Saria, that there would not be more details as to why she vanished into unknown territory in the Lost Woods, as it seems that would be more of a dire situation that required solving. But since it's so vague and unanswered, I don't think it's her.

There are also some theories that Link is looking for Saria because at the very end of the Majora's Mask ending credits, Saria's Song can be be heard. But this song is also the tune for the Lost Woods, as well as the song of friendship between Link and Skull Kid from OoT. It's a well-fitted 'happy ending' tune, as Link returns to Hyrule and Skull Kid rejoins his friends.

Now, on to the main event!

  Why it is not  Skull Kid  

Some believe that Skull Kid is the friend Link was looking for, because the Skull Kid in Majora's Mask is the same one that Link befriended in Ocarina of Time. (Skull Kid confirms this after the ending credits.) People who favor this theory generally do so because it cleanly wraps up the game. However, Majora's Mask is anything but cleanly wrapped, and this theory has plenty of flaws.

1. In OoT, Link's interactions with Skull Kid are completely optional. Playing Saria's Song to him to receive part of a Heart Piece and eventually selling him a mask is the extent of their relationship in-game. In addition, when Link returns to the forest as an adult, Skull Kid attacks him as an enemy and there is no way to remind him of their previous friendship. In a state where Link is almost entirely alone in a terrifyingly dark world, Skull Kid can't even be approached. In the game's grand scheme of fighting enemies, receiving Spiritual Stones and Medallions, and eventually defeating Ganondorf, Skull Kid has zero relevance.
2. There are two key phrases concerning the friend Link is looking for in the MM prologue. One, the friend is beloved and invaluable, and Two, they parted ways when Link fulfilled his heroic destiny and took his place among legends. As the above note explains, Skull Kid most definitely was not beloved and invaluable to Link. As for parting ways, the timeline doesn't match up. Link fulfilled his destiny and became a legend when he defeated Ganondorf and saved Hyrule, at the end of the game. Link technically parted ways with Skull Kid one-third into the game, when he opened the Door of Time and was put to sleep for seven years.
3. Majora's Mask is a game that is filled with philosophical questions and ambiguous meanings. Although Link can try to help as many of the Termina inhabitants that he can, some are beyond help, like the Deku Butler's son, whose forlorn scene is played in every version of the ending credits. Many questions and events go unanswered as well, like the sky portal seen above the Stone Temple, and why THEY steal cows from Romani Ranch. Having the ending be bittersweet as Link leaves to continue a search for his own friend fits the overall game much more than a neatly tied-up package would.

  Reasons why it is  Navi  

Fansite bias aside, Navi is a main contender because of the time she spent with Link during his journey. Regardless of how annoyed players may have been with her, she was a constant companion and knowledgeable guide for a boy fighting alone in an unknown world.

1. Beloved...: Navi joined Link at the very beginning of his journey, and stayed by his side until the very end. No other character in the game shares this quality to that degree. Only once could she not help him -- during the first stage of Link's epic battle with Ganondorf, because his dark powers were too intense for her. But once he was defeated she could help again, and during the second battle declared, "There's no way he's going to hold me back again! This time, we fight together!"
2. ...and Invaluable: Link grew up in a secluded forest with eternal children, an area protected by the Great Deku Tree. This, coupled with the game narrator's consistent "You don't know what that means, but you got ___!" messages, it could be said that Link was a kind but sheltered/naive boy. Stepping out into the vast and dangerous world of Hyrule for the first time, Navi easily provided him info on what things were, who was friend or enemy, and where to go next.
3. Parted ways when he fulfilled his destiny: After Ganondorf was defeated and sealed in the Sacred Realm by the Sages, Princess Zelda returned Link back to his original time to live out his lost years. He was warped back to the Temple of Time as a child, and accompanied with a special tune, Navi floated up and flew out of the window that shone light on the Master Sword. After that, Link then turned and left the temple, and (presumably afterwards) returned to Princess Zelda's courtyard, which is the last scene of the game.

Though the game Majora's Mask itself is mum on whom Link is looking for, the opening scene provides a small hint that nudges toward Navi. When the last paragraph of the Prologue fades, you hear a fairy swish sound, a sound effect also heard in Ocarina of Time. Some argue 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 would the director place that sound there if it was not related to what they players had just read? From a literary standpoint, it would be very misleading if it was not intended to be interpreted that way.

For more outside evidence:

In the official, Nintendo-licensed manga for Majora's Mask by Akira Himekawa, Link is depicted as searching for Navi, and the reason why he enters the Lost Woods.

In the Collector's Edition Strategy Guide put out by Nintendo, it says that Link was looking for Navi.

  Conclusion!  

Link was looking for Navi in the beginning of Majora's Mask. End of story.

The game leaves you hanging at the end regarding it though, because although Link retrieves his stolen ocarina and horse, and saves Termina and its inhabitants from certain doom, he didn't find Navi. That is what has so many people irked, and has them trying to convince themselves that it was Skull Kid instead, so they can have their happy ending.

But Majora's Mask isn't about perfect happy endings. It's complicated, and confusing, and even at the most complete victory it's still bittersweet. This game is about relationships, whether they're close or distant, misunderstood, or loving regardless of faults. And it was about healing, which, considering Link's state after Ocarina of Time's events, was something he really needed too. Link may not have found what he started out looking for, but he did find what he needed.

Part of the game's over-arching plot is how Skull Kid was friends with the Giants, and how when they left, it deeply upset Skull Kid. I see this as a parallel of sorts to Navi leaving Link, and how he may have felt when she left him. The fact that at the end of the game, Link can receive the Fierce Deity mask, an immensely powerful item that is a foil to Skull Kid's Majora's Mask, further cements this in my mind. Both Link and Skull Kid are boys who lost their friends and went on to try find them, though their methods and actions greatly differed.

At the end of the game, the Happy Mask Salesman says that "whenever there is a meeting, a parting is sure to follow. However, that parting need not last forever... Whether a parting be forever or merely for a short time... That is up to you."

So who is to say, whether Link will ever find Navi or not? It may never be told through a game, but the answer will always be open.