If your family has been in Australia for a generation or so, it may be worth subscribing to
www.ancestry.com.au
It is part of an international site, but specific to Australia, so could be a good starting point for finding when/how your family arrived there.
Have a look through the site before signing up, you can always pay per view for $10.95 for 10 items and see what you think.
Ask your family to keep thinking about what they know, or even 'think' they know and write it all down.
Sometimes stories change drastically or are not actually true, but little bits of information often fall into place many years later. Just check every fact twice, then check it again!
Have fun, and good luck with finding your family - I've been doing it on and off for 20 years and am still hooked.
Caroline.
Searching for my great x3 grandfather Raffaele CIACCIA, also known as Raphael/Ralph CHURCH. He was born in Napoli around 1792 and arrived in London before 1812 with his brother Saverio CIACCIA, where they married sisters Ann and Jane FURNEAUX. He switched between CHURCH and CIACCIA all his life, which has made it difficult enough to pin him down. I want to find his origin in Italy.