While Indigenous Australians have inhabited the continent for tens of thousands of years, and traded with nearby islanders, the first documented landing on Australia by a European was in 1606.
The Dutch explorer Willem Janszoon landed on the western side of Cape York Peninsula and charted about 300 km of coastline. Information about his ship and a modern replica can be found on the Duyfken 1606 Replica website. You can see a copy of his map online.
Before this Europeans had long believed there was a land mass in the southern hemisphere which they called Terra Australia Incognita, meaning Unknown South Land.
After Janszoon many Dutch explorers sailed along the northern, western and southern coastline. James Cook was the first recorded explorer to land on the east coast in 1770. He had with him maps showing the north, west and south coasts based on the earlier Dutch exploration.
A timeline of significant landings can be found at the Australia on the Map 1606-2006 website, along with early maps, excerpts from journals, pictures and a bibliography for further references. This website has been archived in PANDORA, Australia's web archive. The publisher's site is no longer current.
There are claims of earlier landings by the Portuguese, Spanish, Chinese, Arabs and Romans, but there is little credible documented evidence.