It should. Note II is a world phone and is sim-unlocked. Some software versions have APN settings uneditable... if you can;t edit those, you will not have a data connection on your Aussie carrier... check the following:
system settings --> wireless and networks --> more --> mobile networks --> Access Point Names
if you can add and edit APNs from the menu above, you are good to go.
it also cant hurt to check what bands the major carriers (optus?) use in Australia and confirm that the Note II also operates on them
OG (Screen Issues) --> DX (Headphone Jack Issues) --> D4 --> Note II