How do miners detect double-spending? 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.  

Spending "coins"
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.

Example:
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 and Y.third.".

X.first   0.03 BTC                       Z.first    0.10 BTC (spendable with Bob's signature)
                       ---- tx Z  ---&gt; 
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 Z spent X.first and Y.third, and converted them to two new "coins" Z.first and Z.second.

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", X.first and 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.".