The following passage from Herodotus ("History", book 4) may be of interest to you:
42. For my part I am astonished that men should ever have divided Libya, Asia, and Europe as they have, for they are exceedingly unequal. Europe extends the entire length of the other two, and for breadth will not even (as I think) bear to be compared to them. As for Libya, we know it to be washed on all sides by the sea, except where it is attached to Asia. This discovery was first made by Necos, the Egyptian king, who on desisting from the canal which he had begun between the Nile and the Arabian Gulf, sent to sea a number of ships manned by Phoenicians, with orders to make for the Pillars of Hercules, and return to Egypt through them, and by the Mediterranean. The Phoenicians took their departure from Egypt by way of the Erythraean Sea, and so sailed into the southern ocean. When autumn came, they went ashore, wherever they might happen to be, and having sown a tract of land with corn, waited until the grain was fit to cut. Having reaped it, they again set sail; and thus it came to pass that two whole years went by, and it was not till the third year that they doubled the Pillars of Hercules, and made good their voyage home. On their return, they declared - I for my part do not believe them, but perhaps others may - that in sailing round Libya they had the sun upon their right hand. In this way was the extent of Libya first discovered.
This reference to the sun could probably not have been made up, so we have to assume that the Phoenicians did on at least one occasion sail past the southern tip of Africa. From there it isn't so much of a stretch to imagine them blown off course and drifting all the way to the Australian shores.