In Ruby, Sapphire and Emerald, Golducks can be found in the Safari Zone by surfing. They are quite rare.
In Pokemon Fire Red you can find them in the Cerulean Cave, the Berry Forest (Surfing), Seafoam Island, and Cape Brink.
It might be easier to get a Psyduck in all those games, and evolve it to Golduck at level 33.
Psyducks and Golducks are not available in Leaf Green, Colosseum and Pokemon XD.