All gas is consumed because the EVM essentially only has 1 exception: Out of Gas.
To see this clearer, take a look at the difference between a "pure" exception, and an error due to bad/buggy/invalid EVM code. Out of Gas is the former. Now there are errors such as stack underflow, invalid JUMP, and invalid opcode: they can be called "exceptions" but they are more like errors than an EVM exception, because the developer of the contract has not written valid EVM code according to the rules of the EVM. For example, an invalid opcode is like writing "class" instead of "function" in Javascript: native Javascript does not have "class", unlike a language like Java. With stack underflow, it's like the developer telling the EVM to add 2 numbers, but the developer does not provide the 2nd number.
Note also how "exception" in the EVM, is different from other languages. For example, there is no divide by zero exception in the EVM (though Solidity 0.4+ will generate an exception for this). Assuming valid EVM code, there are no exceptions except for Out of Gas.
Since there's only an Out of Gas exception, these other errors were made to behave as Out of Gas. This is relatively consistent with some Ethereum design principles of generalization and minimizing complexity. In other words, when implementing the behavior of stack underflow, invalid JUMP, and invalid opcode, it's simpler and easier for the protocol to reuse the implementation and behavior of Out of Gas.
Other answers have explained how Solidity compiles throw to an invalid JUMP. (Serpent instead uses an invalid opcode, and calls it invalid instead of throw.)
EDIT: The Byzantium release includes EIP 140, a new opcode named REVERT in the EVM that:
provides a way to stop execution and revert state changes, without consuming all provided gas and with the ability to return a reason.
throw is being deprecated in favor of revert(), require(), assert()