The northern coast of Australia most definitely gets Tropical Cyclones, and sometimes big ones. Luckily most of that part of Australia isn't all that inhabited. Northeast and West Australia also get storms as well. I believe New Zeland is mostly free of them due to its more southerly latitude -- at least the big ones.

Thinking of Oz, probably Tropical cyclone Tracy is the big one there. It hit Darwin (on the northern coast of oz) pretty hard in 1974. At least that's the one brought up to me the most when I was talking with folks while I was in Sydney.

When you hear of no southern hemisphere storms, I believe they are talking about the South Atlantic. But that was blown out of the water by this years anomoly storm that hit Brazil. Needless to say, tropical systems in the South Atlantic all but never occur.