This was one of the major questions asked at the end of Ocarina of Time, and even more so after Majora's Mask came out. Where did Navi go? As hard as it is to say, I don't think Link found her. He's Hylian, a fact that made holding on to a fairy almost impossible, bonding aside. He's bound by different rules when it comes to interacting with a fairy, more out of convenience and assistance then a friendship. At least that's what it was in the beginning. We attach ourselves to something that cares for us, it's a basic human action, and I imagine it's the same thing with the Hylian race, in particular regarding Link. Young and innocent, thrown in to a dark, and scary world. He fought to keep the company he made, in this case with Navi. It's hard to come to grips with knowing he might have never found her again. The relationship was amazing, the adventure was something to behold, and the defeat of evil should have solidified that connection, but I suppose it wasn't going to happen that way.
Navi was gone.
Link then transitions in to the Termina Universe, something I didn't expect. The split in the time line was an amazing concept back when it was first revealed, but it ends and continues at roughly the same point in time. Now, we know he's looking for Navi in the Child timeline. That's a given, and in doing so, finds Tatl. A sort of replacement fairy for the time being, the connection again was re lit. Link had absolutely no problem allowing Tatl in to his inner circle, even though we all knew she was using him at the start. As with Navi, the relationship turned in to something more. Again venturing in to a dark and dangerous world, Link had the companion he was searching for, albeit, not the one he expected.
With the defeat of Majora's Mask, he was once again thrown in to a hard separation with another fairy. A heart torn goodbye, he sets off to once again venture for Navi's companionship, but it only gets worse. This is my opinion, and the theory was thrown around a few years ago (around the release of TP) that Link never found her, and in the end, perished in what was then the Lost woods. Remember back in OoT, those who venture in to the Lost woods without a fairy would eventually turn in to a Stalfos? Regarding the Child timeline, I think that was Link's fate, to drift off in to history, a Hero, but forgotten through the ages. Never to be heard of again.
Interesting stuff though, and one of the greatest mysteries in the series.