I just got the email myself, it appears that payment information was accessed so they are telling their customers to check the account of the card used, they did not inform users of retention of payment information nor does it look like they used a proxy service, so it appears that they where storing original card numbers on their systems. Fortunately, I use a specific card for online purchase so I will just cancel the card and ask for a new one. I am not real happy about having to go back through transactions and look for fraudulent activity, though.
PayPal is linked to a checking account usually, so I don't see how that's safe. I use one and only one Amex for all online purchases. If anything goes wrong, cancel the one card...start over.