That is actually a good question.
Miners verify transactions and put them in a block they try to mine. This means that every confirmed transaction is checked. So how do they check it?
The blockchain is a ledger that contains all transactions. There you can see when a coin was created and if a coin was spend and to which address it was spend. If there is no further address to which the coin was send, then it is still in the current address.
There is also a list of all addresses that hold unspent Bitcoins, so it is easy to check.
edit: also i think all wallets check if you have sufficient funds.
This is a good and simple explanation.
If someone wants a little more detailed answer here goes. The Bitcoin network is made up of two types of user on a technical level: mining nodes, and full nodes. Both these types user verify all transactions. When a user wants to send bitcoin they make a transaction and announce it to the network using their wallet software. The network of nodes pass transactions to each other. Mining nodes create blocks of transactions (about every 10 minutes) and have the special ability of deciding the order of transactions (e.g. did Bob send a transaction to Suzy or Alice first if they conflict).
When a miner makes a block containing a transaction, that transaction is said to be 'confirmed', meaning the network recognizes that transaction as valid. Due to special circumstances it's possible that a block of confirmed transactions will not remain valid. However, the more blocks that are built on top of that block, creating the blockchain, the less the chance that block might become invalid. As a user your confidence that you actually got paid rests on the number of confirmations a transaction has (the number of blocks built with and on top of the block containing it). People are advised to seek
at least 1 confirmation, but for better security 6 confirmations or more.
edit: also i think all wallets check if you have sufficient funds.
Wallets check this if they are full-node wallets. Bitcoin Core is currently the most popular full-node wallet software. Web wallets that let people use bitcoin via web interface like Blockchain.info usually run full-node software in the background.