hey there Sam,
I also live in Oz and have 2 octos at the moment.
The "common" octopus that seems to be found mainly along the queensland coast is the 'Cyanea'
visit:
http://www.edge-of-reef.com/cefalopodi/CEFOctopuscyaneaen.htm
Both of mine are cyanea, and they are both very playful and have great personalities! They are also one of the few day active octos along the Australian coast, heading south you start to get blue ringed octos - stay away from these is my advise unless you alreay have experience with cephs, it might sound cool to have a blue ringed octopus but it wont be cool if he bites you when your cleaning out his tank or something!!
There are also a few smaller dwarf species but these are all nocturnal and will be almost impossible to catch.
As for catching them....this is a fine art (and a whole lot of luck!!).
We have divers in Qld which bring in fish and live rock for the Auqarium and often they call and say they have either found an octopus lair on the last dive or they send up the babies that quite often come in the rock... this is how i got Julius. I dont like to take them from the reef but if they come up to us in some rock I cant set them free in local waters so i have all these escape proof tanks!!
Are you looking to get an octo? I wanted to start a breeding program similar to Octopets but am currently in discussions with AQIS. We would need to import the eggs most likely from the US, but AQIS say that because there is no formal descision on the importation of LIVE moluscs they cant allow them in at this stage but we are attempting a couple of other avenues. getting them off the reef, sexing them and then hoping they will mate is a bit hit and miss so we'll just have to wait and see... but at least i got to do heaps of reasearch on Australian Octos and environment so if there is anything else I can help you with let me know.
