TL;DR: The network is not made aware of address ownership, nor can anyone check if an address is owned unless it has been used previously (or is owned by himself). Anyone can send transactions to any valid (as in correctly shaped) address¹, the recipient doesn't have to be online for a transaction to take place.
Let me elaborate a little bit in order to explain:
Addresses are the public key of an asymmetric key pair
An address is the public key of an asymmetric key pair. The owner of the key pair can use the private key to sign transactions or messages (for example in order to prove ownership). Only by using the correct private key a valid signature may be created, which then anyone can verify as valid by using the associated address (which, again, is the public key).
Wallets are an abstraction
A wallet is an abstract construct, which contains a set of public and private key pairs randomly generated for the user. In a deterministic wallet, the keys are derived from a passphrase instead of a random seed.
The Bitcoin client software abstracts the wallet for the user such that it checks each of the addresses contained in the wallet, whether there are any balances (transaction outputs) associated in the blockchain with them. It sums the funds up and presents them as a single total balance. Underlying, however, these balances are stored publicly in the blockchain (that's right, the wallet doesn't contain your coins, it just allows you to spend them). They are split up to numerous addresses and transaction outputs:
- Address #15521³ has
- 3 BTC in transaction output 1
- Address #23414 has
- 1.2 BTC in transaction output 1
- 0.7 BTC in transaction output 2
- ...
Everyone can see them, however, usually can't determine the identity of the owner.
Transactions are public notifications of change in ownership
Now, when someone sends a transaction, he basically puts up a notice for everyone in the network to see in which he signs over some of his transaction outputs to recipient addresses. He signs this notice with his private key, so that everybody can check that he is the rightful owner of the outgoing balance (as they can see what address the balance is being sent from they know which public key to use to verify the validity). This can happen regardless of the recipient being online: The bitcoins will be available to spend to the owner of the new address, because only he has the private key, whenever he choses to do so.
It cannot be determined if an address is owned by someone
The public keys (Bitcoin addresses) fulfil a specific pattern with checksums, so that bitcoin software can easily assess whether an address is valid. However, unless an address has been used before there is no way for anyone to check whether a valid address has actually been claimed by anyone.
At no point the network is ever made aware of the creation of new wallets, nor does it have to be. Balances are just signed over to a recipient address and subsequently can only be spent with the associated private key. If the new addresses private key hasn't been found yet, it is very unlikely that anyone ever will do so – the coins would likely be lost forever.
¹ By creating raw transactions one can actually send transactions to an invalid address. This is for example used to leave messages in the blockchain or to validate the authenticity of documents.
³ Of course addresses really are alphanumeric strings with up to 34 characters.
