The Armory of a character is updated upon logging out of said character. This works for gear and talent choices but I am not 100% sure if very recently acquired achievements will show up straight away.
As far as I am aware, all characters over a certain level (10?) appear on the Armory. I also believe that there is no way of making a character 'private'. A user could remove all the gear and talents of a character to hide what they are doing if they so desired.
The majority of character data is public, but some can only be viewed if you log into battle.net of the account which owns the character. The calendar is example of private data.
There are quite a few ways to search for characters on the Armory. By character name, realm, guild and even arena team I think. Other advanced filters exist as well, but I am not very familiar with them.
Hope this helps.
Edit: As Ramhound has pointed out in the comments, upon logging out the armory is not always updated instantaneously. It depends on several behind the scenes factors (i.e. server load, maintenance). The updates are queued however and should eventually happen. Thanks Ramhound.