I'm not convinced that Link went looking for Navi. Originally that's what I thought, and it's still what I like to think, but I recall some kind of proof that it wasn't Navi, or atleast a very convincing theory.
Ultimately he goes looking for a friend and ends up with a friend that he had known in OoT. Skullkid tells him he smells like the boy he used to know, and iirc they accept eachother as friends at the end of MM.
Link seemed pretty okay with Navi totally ditching him in the OoT ending. I guess he got fed up with "Listen!" "Look!" "Listen!!" "Look!" "Listen!" "Listen!"
Think about the symbolism in Link stumbling onto who may represent his potential counterpart, Skull Kid, and how from him are split two faeries, Tatl and Tael, who may be counterpart(s) to Navi. To balance out this equation, both Link and Skull Kid end up with one faerie each, both of which - in Hyrule standards - make up
one faerie. This raises the question that perhaps Link and Skull Kid are one in the same in that one had the ultimate power to destroy Termina, and the other the power to save it - whereas no other individual could accomplish either feat.
Navi was tasked in the very beginning of OoT by the Great Deku Tree to watch over Link and guide him to fulfill his destiny, and so she accompanied him in Hyrule because without her, he simply (and unfortunately) could not accomplish all that he did. Now, because Termina is a polar world to Hyrule, Link fatefully
did not need her. Much can be revealed about Termina's functions if its Hyrulean counterparts are set up in a polarized fashion where "this in Hyrule happens in such a way because in Termina, it happens oppositely", etc, etc. Navi knew that she had to leave Link at the end of OoT so he would search her out and consequently save the doomed world of Termina.
All in all, I believe it is Navi he was looking for.
It's
very interesting to note that in the last scene of OoT, Link is seen approaching Zelda in her courtyard
without Navi. It is a crucial point in the story that she recognizes him as the hero from her dream because he is clad in green and has a fairy. Now, he does
not have a fairy, so obviously he will not be saving Hyrule from Ganondorf, so rather than rely on him, she turns to the royal power to stop Ganondorf from taking over. This further asserts that Navi is in fact gone, and Link has gone to look for her because he knows that without her, he could not save Hyrule (which he may believe he needs to do once more), but instead, becomes wrapped up in Termina, and upon
possibly returning to Hyrule after the events of Majora's Mask, learns that Ganondorf has already been sentenced.