The answer to "how do they know" is that bitcoins are created by solving a cryptographic function. Once somebody has solved the function, they submit the solution to the network. If a sufficient number of other nodes on the network agree that the solution is correct, the person is awarded the bitcoin. Transactions occur the same way. The recipient says, "I have received bitcoin number 1234567, and here is the solution to the cryptographic function that proves it." The recipient can only have the correct solution if the current owner of that bitcoin has transferred it to them (or if they have stolen the wallet containing the bitcoin). Again, the network checks the solution and if it is correct, the network notes that the new wallet "owns" the bitcoin.
The record of every single transaction that has ever occurred is known as the "blockchain", and it is by verifying the blockchain that new bitcoins are "minted", and transactions are validated. So computers who are trying to "mine" new bitcoins are the same ones who are doing the work of verifying that existing transactions are valid. The blockchain is absolutely verifiable, for every single transaction, all the way back to when the bitcoin was first mined.
The main vulnerability in this consensus-based model is that if a hostile entity were to control more than 50% of the nodes on the network, they could lie about whether a given transaction was valid, and they would overrule the "honest" computers. In other words, they could say, "all the bitcoins in the world get transferred to me!" Everyone else in the world would say, "No. Not valid." But they would be out-voted. Currently, though, this would require resources on the scale of a nation-state, or a very large corporation, to accomplish. And the massive disagreement between the nodes would surely be noticed immediately.
Here is a good overview of "how bitcoin works".
http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/