Caroline Eliza Carlsen & Carl Olaf (Carlsen?)

I am very interested in finding any information about my great grandfather who travelled from Oslo to Queensland, Australia in 1880. We do not know his birth date, but know that he was born in 1877 in Oslo and was three years old when he left Norway. He travelled from Norway to Australia with his mother Caroline Eliza Carlsen. We have only ever known my great grandfather as Carl Olaf Steffensen as on 12 March 1881 his mother Caroline married Swend Steffensen at Rockhampton, Australia. We guess Carl must have then taken on his stepfathers surname. We assume that Caroline travelled using the name of Carlsen. On the marriage certificate to Swend her name was given as Caroline Eliza Carlsen. Her mother is shown as Hannah Elizabeth Anders and father Carl Ellensen. Caroline was 28 when she married Swend so must have been 27 or 28 when she travelled to Australia. Caroline was born in Olso. They later lived in Bundaberg (not far from Rockhampton). After Swend died on 6 October 1901, Carl and Caroline travelled to New Zealand in 1901. They lived in New Plymouth (where my family lives today). Carl died in 1944. Both he and his mother are buried at a local cemetery. I would appreciate help locating any information including the ships they travelled on. My ultimate goal is to find out Carl's birth date so we could perhaps obtain his birth certificate and find who his birth father was. Looking forward to hearing from you. Lisa Steffensen