How do banks use encryption in ATMs, and where is ATM-related data stored?

Banks use specialized hardware for the encryption, all PINs (for example) are validated from the HSM (Hardware Security Module).

HSMs support a wide variety of encryption and key-management. Thales is the world leader in this field and pretty much has the market cornered on this front.

Encryption support:

Cryptographic algorithms supported:

• Symmetric
• AES (128, 192, and 256 bit)
• Aria (128, 192, and 256 bit)
• Camelia (128, 192, and 256 bit)
• Triple DES (112, 168 bit)
• Asymmetric
• RSA (1024, 2048, 4096, 8192 bit)
• Diffie-Hellman
• DSA
• ECC Suite B
• Hashing
• SHA-1, SHA-2 (224, 256, 384, and 512 bit)

Source: Network-attached HSM: nShield Connect