Manda,
The info is all online.
It is a good thing to order the marriage certificate of Catherine & Khan/Albert. It will guide you further as to his parentage

Indexes for QLD (go to family history research then historical search index) you can find all the births deaths and marriages there... registration numbers are available for ordering certificates

http://www.justice.qld.gov.au/justice-services/births-deaths...

For NSW

http://www.bdm.nsw.gov.au

You can also search the Queensland state archives, just google that one..

If you need further assistsnce just yell out !

Debbie