What prevents a transaction being added to the block chain twice? As I understand it, a transaction basically consists of a from address, to address, amount and some component that verifies that the owner of the from_address has requested the transaction. A transaction is broadcast to the network in the hope that it will get included into a freshly mined block.

If the miner can choose which transactions to add to a block. How does the Bitcoin protocol stop a miner from re-adding an existing transaction to the chain? and thus recreating the transaction and doubling the effect of the transaction.

Surely it is not feasible to search the entire transaction history to make sure the transaction hasn't already been included.

EDIT - from a bit of further research, it looks like including a confirmed transaction will render a block invalid and it will be rejected by other Bitcoin nodes. But how can you determine if the block contained an already confirmed transaction in an efficient way?
In Bitcoin, each full node follows all transaction activity on the network by digesting the blockchain. To that end, every full node enforces their ruleset on the data that they receive. As (usually) the full nodes all follow the same ruleset, every node indivdually converges on the same state.
Hereby, the blockchain's transaction data represents a journal of the activity, which if digested according to Bitcoin rules yields a ledger of all balances at the current blockchain tip, the Unspent Transaction Output Set (UTXO Set).

Every full node maintains this complete set of UTXOs. Each UTXO is uniquely identifiablee by the transaction it was created in, and the position in that transaction's output list.

When a transaction is confirmed, the UTXOs in the transaction inputs get spent and removed from the UTXO set, while the transaction's outputs in turn get added to the UTXO set. If someone tries to replay the same transaction again, the referenced inputs are no longer in the UTXO Set as they were previously removed and the transaction is just as easily identified to be invalid as a transaction spending made-up UTXOs.