How does the Bitcoin client check for double spend?
Bitcoin-Qt marks outputs as spent in the database once they are spent. To check whether an input's prev-out is spent, Bitcoin just needs to look up the transaction and check whether the output is marked spent.

Other ways of doing it are to have a set of all unspent outputs and check whether the prev-out is in this set (future versions of Bitcoin will do something like this), or to index inputs by their prev-outs.