There are two possible sets of records to search.
Firstly, the National Archives of Australia holds online departure records from various ports.
Although incomplete for the early 1900s, and not specifically for deportees, this may help start your search.
In my experience, the responses to their Enquiry Form are very helpful in narrowing down your search. Initial enquiries are free.
Secondly, the court records to find the sentence of deportation.
Court records are more commonly kept by the Public Record Offices of the individual states. (e.g. Victoria). Records of deportation are more likely to be held at these locations.
Unless you can narrow down the date, you may have a very long search on your hands.