Also consider cash-back rewards cards (assuming they're available in Australia) if you don't fly frequently and don't want to be tied to a single airline. Not glamorous, perhaps, but if you use the card for EVERYTHING and pay the bill off 100% at the end of each month, you'll accumulate a tidy sum of cash which you can apply to the purchase of your next airline ticket.

The key is not to get fixated on any one type of reward, but to find a combination (whether it's cash back, hotel points, frequent flyer miles, or something else) which works for you.