Go to my page for a fairly complete discussion on where to get cigar boxes in Australia and many emails from Lori Wimberley regarding the extensive cost of sending from US to Australia as well as the customs problems. Cigar boxes harbour bugs which Australia doesn't like and you may be required to have customs fumigate them at additional cost.
Do as I have done - visit all the tobacconists you can find. Sometimes you get lucky. I found 6 nice boxes last week for only $2 each. Unfortunately such shops in Australia usually have a very low turnover of boxes so you probably will not find in large quantities and it may be months before you can get more from the same place.