Just to say it my way, first, an "oracle" in cryptography is based on the concept of a mythological oracle; a person with a direct line to a deity, and thus with access to information that mere mortals do not have. In cryptography, oracles are "black boxes" that can perform tasks that would be difficult for the attacker, and can thus give an attacker information that is normally difficult to obtain.
A padding oracle, specifically, can tell the attacker whether a message he inputs into it is properly padded (most block cipher modes use some form of removable data padding to ensure that the message length is an exact multiple of the cipher's block size). It does this by attempting to decrypt the message, and behaving differently when a block is or is not padded correctly, such behavior differences being visible to the attacker. The padding oracle is usually an unwitting participant; the attacker typically hijacks an initialized cipher implementation, feeding it specially-crafted messages of his choosing in what's known as a chosen-ciphertext attack.
A related type of attack is a timing attack; it's one way that a decryption implementation can be turned into a padding oracle, by measuring the time it takes to determine whether the block is properly padded. Some cipher modes, like CBC, can be decrypted in any order, and so some implementations will decrypt the last block first to check the padding of the message, in an attempt to "fail fast" on corrupted messages. However, the difference between the time it takes to check the padding and to attempt to decrypt the full message can be used by an attacker to determine which of the two happened, even if the error shown to the attacker is the same in either case.
To guard against these types of attacks, there must be no discernible difference in behavior between an attempt to decrypt a message that is not properly padded compared to one that is. The best known way to do this is to incorporate a secure checksum known as a Message Authentication Code. This MAC is typically produced by a secure "keyed hash", using the same key that encrypted the message. The message is first encrypted, and then the ciphertext, along with information about how it was encrypted such as the cipher algorithm, cipher mode, key size, block size and IV, is hashed using the MAC algorithm and the same key.
To decrypt, the algorithm first recomputes the MAC given the ciphertext and ciphering information shared between the two computers. If the computed MAC does not match the one included with the ciphertext, decryption fails; either the message, MAC or both have been changed in transit by some means, either benign (data corruption) or malevolent (attempted attack).
The chances of an attacker, not knowing the key, being able to change the ciphertext and its MAC in a consistent way is believed to be difficult, and by that I mean a roughly 1 in 2^(keysize) chance, so the strategy of systematically changing the message becomes less efficient than simply trying every possible key. In addition, because the same operation, which pretty much always takes the same time, can detect any post-encryption data issue that would make the message invalid, an attacker can't tell the difference made by any systematic change to the ciphertext and MAC; it either matches (extremely unlikely; see above) or it doesn't (much more likely).