A deterministic wallet derives keys from a single starting point known as a seed. The seed allows a user to easily back up and restore a wallet without needing any other information and can in some cases allow the creation of public addresses without the knowledge of the private key.

Early clients such as the Satoshi client generate a buffer of fresh random private keys to be used as receiving and change addresses in the future. This has the effect of invalidating backups after a short period when the keypool buffer (typically 100 addresses) is exhausted. Deterministic wallets can generate an unlimited number of addresses on the fly and as such don't suffer from this issue. As the addresses are generated in a known fashion rather than randomly some clients can be used on multiple devices without the risk of losing funds. Users can conveniently create a single backup of the seed in a human readable format that will last the life of the wallet, without the worry of this backup becoming stale.

Hierarchical deterministic wallets are described in BIP 0032. These are fully implemented in Coinomi. The seed is a random 128 bit value presented to the user as a 12-24 word mnemonic using common English words. The seed is used after 100,000 rounds of SHA256 to slow down attacks against weak user-chosen strings.

(This description was republished from Bitcoin Wiki.)

Here is a great write up on HD Wallets and here is another.