Your wallet is a collection of private keys and a record of the transactions relating to them. By default your wallet has a key pool of 100 keys. So when your wallet is created, around 100 private keys are randomly generated and stored in your wallet.
Each private key has a corresponding public key, and each public key has a corresponding address. A public key isn't "the same thing as" an address, but there is an algorithm that can give you the address corresponding to any given public key. The reverse isn't true. There are many different public keys for each address, since public keys are 256 bits wide and addresses are only 160 bits wide.
When you click 'new address' in the 'receive coins' tab of the client, it will show you an address you've not seen before. It is taken from the 100 address keypool. The keypool is topped up when possible to always contain 100 unseen addresses. If your wallet is encrypted then it's not possible to top up the keypool until the wallet is unlocked with the passphrase.
Also, when you make a transaction out of your wallet, it's quite likely that the amount you are sending doesn't exactly match the sum of any of the inputs you currently have private keys for, and so some 'change' needs to be sent back to your wallet. When this happens an address from your 100 address keypool is used to receive the change. In this case the keypool will be immediately topped up, since your wallet will need to be unlocked since you're spending coins.
This all happens behind the scenes - you won't see any evidence of it happening unless you look at the blockchain.