Excuse me but are you actually considering undertaking the legal union here in Japan? IMHO that would be an unduly lengthy process. If you simply want to have a wedding ceremony - all the pomp but none of the legality - then the links already supplied would suffice, and my common sense guess would say it wouldn't be all that difficult. In fact I doubt very much that ANY paperwork would be required for such a ceremony, save perhaps the Shinto priest might want to confirm that you are indeed a couple. A clear photocopy of your Australian marriage certificate would probably be enough.
Remember you don't legally marry in a temple or church or whatever in Japan. The legal union takes place at City Hall and for gaijin/Japanese couples the paperwork is not immense, but nevertheless inconveniencing. I don't know the laws in Australia - is there an established church with priests empowered to undertake legal unions?
Whatever, good luck!