A deterministic wallet is a system of deriving 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.
See also: Deterministic Wallet Tools
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.
Certain types of deterministic wallet (BIP0032, Armory, Coinkite and Coinb.in ) additionally allow for the complete separation of private and public key creation for greater security and convenience. In this model a server can be set up to only know the Master Public Key of a particular deterministic wallet. This allows the server to create as many public keys as is necessary for receiving funds, but a compromise of the MPK will not allow an attacker to spend from the wallet. They can alternatively be used in Electrum and Armory to enable completely offline storage and spending, where an offline computer knows the private key and an online one knows only the MPK. Transactions spending coins are ferried between the two computers via USB storage which avoids exposing the offline computer to a network-based attack.
Deterministic wallets implemented by hardware wallets (TREZOR) keep the generated private keys offline and do not expose them to the computer even when spending coins.
Type 1 deterministic wallet
A type 1 deterministic wallet is a simple method of generating addresses from a known starting string, as such it does not allow advanced features such as a Master Public Key. To generate a private key take SHA256(string + n), where n is an ASCII-coded number that starts from 1 and increments as additional keys are needed.
This type of wallet can be created by Casascius Bitcoin Address Utility.
Type 2 hierarchical deterministic wallet
This wallet type is described in BIP 0032 and is fully implemented in TREZOR, Electrum and CarbonWallet. The seed is a random 128 bit value presented to the user as a 12 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. .
The initial description and workings of this wallet type is credited to Gregory Maxwell. 
Armory deterministic wallet
Armory has its own Type-2 deterministic wallet format based on a "root key" and a "chain code." Earlier versions of Armory required backing up both the "root key" and "chaincode," while newer versions start deriving the chaincode from the private key in a non-reversible way. These newer Armory wallets (0.89+) only require the single, 256-bit root key. This older format is intended to be phased out in favor of the standard BIP0032 format.