There are two stages that affect double spending transactions.
Initially, when the transactions are unconfirmed, a node can't know which transaction was "the first" or the "double spend". Through a local policy it can pick either, usually the first it sees. But it might pick the other one depending on for example the amount of fee (Miners might prefer the highest fee).
As soon as one of the transactions is confirmed (6 confirmations to be sure), the other will be invalid. A Bitcoin node maintains an Unspent Transaction Ouput (UTXO) set. Whenever a transaction spends an output (of an earlier transaciton), that ouput is removed from the UTXO set and any outputs of the new transaction are added to the set.
A double spend transaction would be trying to spend an output that is not in the UTXO set and is therefore invalid.
The UTXO set is currently about 1 GB and is kept in memory, to make all the lookups very fast. There are optimizations in the works that would reduce this size. Although with larger Bitcoin adoption the UTXO set will also grow again.