I've never had my card details fraudulently obtained, however I guess I'm fortunate enough to know what I'm looking for in terms of skimming devices or EFTPOS machines which have tampered software.
As much as a I don't like Paypal as a company, I use them for almost every purchase I make online, particularly overseas ones. It adds an extra level of protection and if something does go wrong, you're more likely to get your money back.
I would also advise to cover up your PIN whenever you use an ATM or EFTPOS machine with both hands. ATM skimmers normally rely on a small pinhole camera to capture your PIN in addition to card data. On the subject of ATMs, give the card slot a good wiggle, skimming devices are normally just taped on.
Use alternative methods to pay bills, for example, I pay all my bills online but I manually transfer the amount using BPAY (via my internet banking) or do a once-off direct debit request. It takes no additional time and it saves me those 1-2% credit card transaction fees.
If you must use credit cards, insist on a low credit limit. If a bank refuses to lower your spending limit or apply extra security measures, I would reconsider using that bank. For example, I use Visa Debit which is linked to my normal savings account, but I can stipulate my own daily transaction limits for card transactions. The default is $1000 per day but I can decrease or increase that anywhere up to $10,000.
Finally, get into the habit of checking your statements/internet banking frequently. I check mine at least once a week.