In Australia, EFTPOS terminals (stands for Electronic Funds Transfer at Point Of Sale) either work via an encrypted tunnel over an Internet link, similar to virtual private networks, or a dedicated phone line. According to a page that a friend found on my behalf, the information is encrypted with the DES algorithm - see
http://school.maths.uwa.edu.au/~praeger/teaching/3CC/WWW/chapter5.html#tth_sEc5.5
Thankfully, banking law in Australia makes the bank liable for fraudulent transactions, not the customer. In this case, the banks are wearing the costs of these skimming activities, customers are having the money refunded into their accounts.
The card that I had cancelled is used to access both an everyday transaction account (what you guys in the US call a 'checking' account) and a Visa credit card. The bank wanted to cancel the card and re-issue to protect not only my money that's in the transaction account but also the line of credit in the Visa account, as someone with access to the card details could use it to take money from either account. We should all have our replacement cards in a week or so with luck.
The unofficial word is that people have engaged in some clever "social engineering" to get these cards skimmed. It seems that people have turned up at stores and claimed to be there to perform essential upgrades to the EFTPOS network. They've then somehow programmed the terminals to store card information and forward it to some other location - that's how they're getting hold of people's card details apparently.