How does blockchain.info detect double spends?
All valid transactions are relayed through the network. A client does not know which transactions will be a part of a block, so it stores and relays both double-spent transactions. If you regularly poll your bitcoind, you can see every transaction before it is put in a block. Then it is just a matter of checking txin data for duplicate inputs.