Has there been evidence of ancient Chinese exploration of Australia? Specifically, up through the Middle Ages, before there was extensive contact with Europeans?
Is there evidence of Chinese exploration of Australia (before European contact)?
There is no tangible evidence that Chinese explorers (or traders or any other Chinese for that matter) did land in Australia before the European exploration of the continent began. No Chinese ship wrecks in Australian waters, no Chinese records of having visited Australia, no Chinese artefacts in Australia, no remnant populations of Chinese expeditions, no invasive species introduced from China, nothing, nothing whatsoever.
That said, we can, of course, not rule out expeditions that might not have left any evidence or that left evidence which has just not been found yet. The Chinese were busy people and able seafarers; they regularly visited south east Asia for more than 1000 years. In fact, they tried to conquer Indonesian states in the 1200s and there is a significant Chinese minority in south east Asia that descended from Chinese traders. They were certainly able to go to Australia, and maybe they did.
Of course, there are fringe historians such as Gavin Menzies who profess to know that the Chinese were in Australia in the 1400s (and everywhere else short of outer space for that matter). Though this is occasionally cited in mainstream media it is not considered credible.
Is there evidence of other non-European exploration of Australia (before or after European contact)?
Well, there is clear evidence of Indonesian fishermen frequenting Australian waters from at least the 1720s. (Note that by that time, large parts of Indonesia were actually under European rule. But said fishermen were not controled by the colonial government of Batavia.) They were mainly after sea cucumbers, but apparently introduced new species (tamarind trees), left artifacts, had enough interactions with native Australians that the latter could produce rock paintings depicting a Makassan prau, and there are Indonesian records of said expeditions. For details, see wikipedia. This was after the start of European exploration of Australia (1606) but before the start of European settlement (1788) and the genocides against native Australians (promptly following European settlement).
Some Chinese Qing dynasty coins from the 1700s have reportedly been found on an island off Australia; see here and here. They could, of course, have been brought there by the said Indonesian fishermen (who certainly had contact with Chinese traders) or they could have been brought there at a later date. In any case, this would point at a time when China was already very much on the defensive against European powers.
There are native Australian legends about another group of people who visited Australia, called Baijini, which has been conjectured to mean 白人 (bái rén, "white people" in Mandarin), 北人 (běi rén, "northern people" in Mandarin), or 北京人 (Běijīng rén, "people from Beijing" in Mandarin). Needless to say, this is by no means certain and in the absence of other evidence doubtful.
Coins of medieval African origin have been found in Australia; this is a bit odd, but unrelated to the present question about the Chinese.
Finally there must have been prehistoric contacts a few thousand years ago. Among other things the Dingo was introduced, which greatly uprooted the Australian eco system. But again, this is certainly unrelated to China; the Chinese state in its present form did not yet exist at the time.
Why did the Chinese not discover Australia?
Chinese seafaring and exploration was very different from European seafaring in the age of exploration. China was almost always ruled by (one or two) centralized states; the central government always attempted to maintain a tight control over their population and their population's activities; they generally did not encourage emigration and settlement overseas (except in Taiwan after driving out the Europeans and incorporating it into the empire); they never attempted to establish colonies (except in Taiwan).
They did occasionally send armies overseas with the objective of turning other states into Chinese vassals. Usually such efforts were devastating for those local states (especially if the Chinese commander would, as Zheng He did in Sri Lanka, decide to arrest the king and send him to Beijing to bow before the Chinese emperor). But China was interested in symbolic dominance, gathering tribute, and controlling and securing trade routes, not in colonization. They thus concentrated their efforts on other well-developed countries such as Malacca, Java, India, Sri Lanka (as well as Japan and Korea, and possibly briefly, under Zheng He, east Africa). They had little interest in regions populated by tribal societies such as Australia.
If they did explore Australia, they were doubtlessly pretty disappointed in what they found.
Further, there is a downside to be organized as a centralized state. A quirk of internal Chinese politics after Zheng He's voyages, saw the Chinese naval efforts stopped by the administration, and much of the procedural knowledge and human capital they had in this area destroyed and forgotten. Had this turned out differently, history might have taken a different course and it might have been the Chinese, not the British who murdered the native Australians by the tens of thousands.