If you were married in Australia, you must provide the marriage certificate issued by the Australian Registrar of Births, Deaths and Marriages (RBDM). To apply for an RBDM certificate click here; http://www.australia.gov.au/information-and-services/family-and-community/births-deaths-and-marriages-registries
If you were born in Australia but married outside of Australia, you will need to register a change of name with RBDM in the Australian state or territory of your birth and obtain a name change certificate. You must also provide your original overseas marriage certificate with the passport application. To apply for an RBDM certificate click here; http://www.australia.gov.au/information-and-services/family-and-community/births-deaths-and-marriages-registries
If you were born outside of Australia, married outside of Australia and normally reside outside of Australia your foreign marriage or foreign change of name certificate must be legalised by the country of issue. If you were married in the UK, you must send your original marriage certificate to the Foreign and Commonwealth Office (FCO). To find out how to do this, click here; https://www.gov.uk/get-document-legalised
If you were born outside of Australia, reside outside Australia and have changed your name by UK deed poll, you will need to follow these two steps;
1. Have the document ‘certified’ by either a solicitor or a notary public
2. You then must have this legalised by the Foreign and Commonwealth Office (FCO)
To find out how to do this, click here;
If your document is issued by a government authority other than the UK, you should contact the Embassy or Consulate of that country to obtain information on how to legalise this document.
Change of name – fee waiver
If you are applying for a new passport and you have changed your name as a result of:
• entering or ceasing to be in a registered or de facto relationship; or
• as a result of transitioning to another gender; and
• your passport was valid when the event leading to this change occurred, your replacement passport may now be issued free of charge with the same expiry date as the passport being replaced.
You are no longer required to lodge your application within 12 months of the event to qualify