POODLE is primarily a padding oracle attack against SSLv3.0, which is inherently vulnerable to the attack due to the protocol design. The "on downgraded legacy encryption" part of POODLE's name comes from the fact that most SSL/TLS client implementations will allow a TLS connection to downgrade to SSLv3.0 if the handshake fails - see this answer for more detailed information around TLS downgrade attacks. Since an attacker in a man-in-the-middle position can simply drop or mangle packets, it is relatively trivial to cause a TLS connection to downgrade to SSLv3.0, which then becomes vulnerable to the padding oracle attack against CBC.
SSLv3.0 only validates that the padding byte length is ok, and doesn't require the actual padding bytes to be checked for validity; they can be anything, as far as the protocol specification is concerned. Furthermore, the padding is not authenticated; it uses a MAC-then-CBC method. The padding oracle attack works by causing the padding data to move across a block boundary (this can be done by increasing the plaintext length until the ciphertext length increases by one block) and then swapping out the padding block for any previous ciphertext block. If the decrypted result has a final byte of value equal to the expected padding length, it will be accepted, which leaks the value of a single plaintext byte. As the process is non-deterministic due to the random IV per connection, it should take at most 256 connections to leak each byte. The attacker can then shift the position of the target plaintext within the connection by one byte and attack it again, repeatedly testing via the oracle and shifting across until all target bytes have been revealed.
The normal recommendation for POODLE where SSLv3.0 cannot be disabled entirely is to implement TLS_FALLBACK_SCSV support. As this answer describes, this flag forces the negotiated connection to use the highest possible supported protocol version, which is mutually authenticated by the use of exchanged Finished messages, thus preventing downgrades outright.
There is a secondary variant of POODLE which works against certain implementations of TLS, instead of just the SSLv3.0 protocol. The key point here is that the vulnerability is not inherent to the TLS protocol at all, but rather is exploitable only in cases of poor implementation. The reason that sensible implementations of TLS (see note below) are protected against POODLE is that the CBC padding is fully validated at the server side (i.e. all padding bytes must be equal in value to the integral size of the padding, and the server must check this fact). This makes attacking the padding significantly more difficult. However, it was found that some implementations of TLS did not check the padding correctly, and were still vulnerable to POODLE.
(note: the TLSv1.0 specification does not state that padding must be checked; this requirement was introduced in TLSv1.1 and continued in TLSv1.2. As such, TLSv1.0-compliant implementations may still be vulnerable to POODLE, hence why I used the term "sensible implementations" rather than "compliant implementations" above.)
