The difficulty has always been in registering an older boat that has never been registered previously. Theoretically you need to have docs going back to the original builder but I do believe there is a way around this. I looked into it when we bought Raven as one of the boats we were looking at was not a registered ship.
In a similar train to what Simon says, it actually isn't all that difficult over here - and, yes, fortunately the AMSA Shipping Registration people are very friendly and helpful.
I know because we came unstuck registering Bungoona because the PPO (previous-previous owner) moved to Queensland without telling AMSA (an offence under law) and sold it to the PO without the Registration Certificate.. In the end, with both the PO and PPO dead and buried, we had to cancel 50 years of history and pay $799 to re-register... but I'm getting off track.
All you need to do is get a Builders' Certificate from the builder (there will usually be one) and/or have the boat measured by a Marine Surveyor, be able to show a "Contract of Sale" document signed by the PO and then sign a Stat Dec declaring you are the legal owner and another declaring you've got the name, port etc marked as per the regs, all witnessed by a JP.
Given that ANY vessel entering or leaving Australian waters must be registered, it's not in their interests to make it TOO difficult to do..
On a side note: It's actually illegal in this country to fly the Red Ensign without being a Registered Ship. If ever you see some fancy new stinkpot roaring though the mooring field flying the Red Ensign to impress their friends, check to see if their name and port appears in the AMSA list - AMSA will happily book them if it doesn't!!..