Assuming I spent 1BTC, then waited a few months and then spent it again. How is this detected? Do the miners go through the entire blockchain to assure the coin was never spent before?
The other two answers explain what has to be done to discover doublespends. I'll try to explain how it works.
There are no "balances", there are "coins"
A common misunderstanding is that there is a register of balances for addresses, and when you spend bitcoins, some of your balance gets deducted from your address. Actually, that's not a good description of what's happening. Under the hood, it's more akin to receiving a "coin" whenever you get paid, and drawing upon your available "coins" when spending.
When someone sends you a transaction, they create an "unspent transaction output (UTXO)". This UTXO is uniquely identifiable e.g. the first output of the transaction with the id
X. UTXOs are like coins: They have a specific value and can only be spent completely. To spend part of one, you have to give up the complete coin, get back change.
You have two Unspent Transaction Outputs ("coins") worth 0.03 BTC and 0.09 BTC. They were created as "first output of transaction
X" and "third output of transaction
Y" respectively. You want to send 0.10 BTC to Bob.
You cite these specific two UTXOs as inputs to your transaction
Z. I.e. you order "I want to spend the first output of transaction X, and the third output of transaction Y. I'm converting them to first and second output of transaction Z. – Here are the signatures for
X.first 0.03 BTC Z.first 0.10 BTC (spendable with Bob's signature) ---- tx Z ---> Y.third 0.09 BTC Z.second 0.02 BTC (spendable with your own signature)
In this example, you use up your two "coins", to give one "coin" to Bob to pay 0.10 BTC, and get back the change as another new "coin" which goes to yourself. Your transaction
Y.third, and converted them to two new "coins"
Now, as described by Greg and Jestin, every full node has worked through the whole blockchain. Every single transaction references one or more "coins" that get spent, and creates new "coins" as in the example.
While a node works through the blockchain, it keeps track of the "coins" that exist, and updates this database with every transaction that happens. The database is referred to as the Bitcoin network's "Unspent Transaction Output Set". So, when you're up to date, the node has a list of every "coin" that is available for spending.
Back to the question
So, you sent 1 BTC to Bob one month ago. Now, you're trying to use the same "coins",
Y.third a month later to send money to Carol. The nodes look at their "coin" database, and see that they are not in it. They can immediately say "Those coins have already been spent.".
Yes, miners check the blockchain to ensure all new transactions are valid before including them into a block. However, it also depends on your definition of "miner". If you mean the people running ASIC miners as part of a mining pool, then no, they do not generally check for the validity of transactions or blocks. They simply hash block headers to calculate nonces. If you mean mining pool operators, then yes, they need to check the validity of transactions and blocks, otherwise the blocks their pool produces will be rejected by the rest of the network.
Also, miners are not the only nodes on the Bitcoin network that validate transactions. Full nodes, which relay transactions through the network, also perform checks to ensure transactions are valid before relaying them to other nodes. You would have a very hard time even getting your invalid transaction to a mining node, let alone having it included in a block.
Yes, they do. Mining software indexes the blockchain database so that lookups like this are relatively quick (that is, they don't have to laboriously search through gigabytes of transactions).