When you spend, you are spending a transaction that you hold the key to.
Saying that there are no addresses is a slight exaggeration. But a useful one. Smile and think of the kid from the Matrix telling Neo that there is no spoon, while he is holding a spoon.
Lots of people get stuck in their thinking because they expect the address to be a proper entity that tracks the balance sent to and from it.
Your balance is the sum of the values of the transactions that you can spend, that is, transactions that you have the key to, and that haven't already been spent. When you make a new spend, the client grabs one or more of them, completes them using private keys from your wallet, and creates one or more new outputs.
And yes, the private key is just a random number, the public key is just derived from multiplication (funny multiplication) from that private key, and the address is the hash of the (hash of the) public key.
If you want to really get into it, transaction outputs are actually scripts. Addresses are used to create the (incomplete) scripts, and then redeeming them later involves adding the missing parts to complete it. To complete the script, you sign the partial transaction with your private key and provide the public key that corresponds to it. That way, anyone can verify that the script was signed by the holder of the private key that corresponds to the public key in the completion, and they can also hash the public key to get the address that it was sent to, to verify that the keypair used to sign it is the keypair that it was intended to go to. Oh, except that there are other script types, and BIP16 P2SH lets you make complicated scripts that are presented at completion instead of at creation, and...
Really, dree12's chart explains it all very well.