The legend goes that it derives from their national rugby union team.
A sports writer for the UK Daily Mail in 1905 commented that the NZ team of the day in a match against played like a team of “all backs”. Somehow that got corrupted in a printing error to form the headline “New Zealand All Blacks”. The name stuck and the team adopted an all-black strip.
The only problem with this legend is, of course, that the team was already playing in a mostly black with some white strip. There’s a good chance that it was chosen so as to contrast with the English strip of the time which was all white.
The Australian green came from the caps worn by its cricket team, which were originally blue, but were changed so as to contrast with the English. The 1899 touring team carried jumpers banded in the colours of “gum green and wattle gold”.
The original Australian rugby strip was actually blue and maroon, representing the two major colonies’ unions - the maroon of New South Wales and the dark blue of Queensland (later NSW moved to a sky blue and Queensland, in response, took the maroon). Both the rugby league and rugby unions changed to a green-and-gold strip in the 1920s - the league team to a green guernsey with gold highlights, the union team to a gold guernsey with green highlights in order not to clash with South Africa.
And, Mahaloth, in my experience every country with “yellow” as one of their colours uses the term “gold” - as a pseudoarmitage thing. Same colour, but everyone calls it “gold”.