Link has alwasy, traditionally been left handed (not ambidextrous), but this changed as the Nintendo controls became more personal.
Link has been left handed in every game except for those on the wii (TP and SS). The only reason he is right handed on the wii games is because Nintendo knew more right handed people than left handed people would play the game and they wanted the controls to feel comfortable. But, according to Canon, Link is Left handed. TP's Gamecube version is the "official" version, and Link is left handed. The only game that Nintendo has made Link "officialy" Right handed is SS and I believe it is only because of the evidence above.
This should be common knowledge by now. Link has always been left handed but as the Wii came out, as RedDukuScrub described, Nintendo decided to mirror mode TP (on the gamecube everything is the complete mirror opposite then it is in the Wii version) due to the fact Nintendo felt the majority of players were right handed, thus if Link were to be left handed in the game it might not work so well with the Wiimote controls, (players swinging sword with right hand, Link swinging sword with opposite hand) so the GC version of TP was flipped around entirely for the Wii version (so it would appear link is right handed on the Wii controls would be appropriate for right handed users ont he on screen results): you may play both versions to compare if you wish.
There was a bit of on uproar about this by fans as the two versions of TP were announced. I was one of these people, actually - breaking tradition is a big no-no. but i understand the logic behind it. But if he ever showed up right handed in another version (such as say, a DS game), I would be semi-furious.