I thought that fees and such were only incurred when you ran your debit card as a credit card transaction, with signing your name and such - I was under the impression that using your PIN number and using it as debit didn't incur those costs.
Debit cards issued by Visa or Mastercard and operating over those networks incur a lower fee than credit cards but follow the same interchange fee structure. Australian Visa interchange fees are here: http://bit.ly/visainterchangefees. Just incase anyone was interested. Whether or not these cards require a PIN or signature depends on whether they use the Chip-and-PIN system, which all new cards issued in Australia should.