How does change work in a bitcoin transaction? It seems that when you send a bitcoin transaction, all the coins in the sending address are spent in that transaction, divided into the amount that you intended to send, and "change", which goes back to you, but at another (newly created) receiving address.

That makes it a bit difficult to track your balance on block explorer (especially since the new receiving address does not seem to be displayed in the Bitcoin client anywhere).

Does it have it have to work like this, or is this a specific implementation detail of the client software? 

Also, do you have to wait for change to be confirmed before you can spend it again?
First, let's clarify the difference between accounts and addresses.

"Accounts" are used for the convenience of people to track their funds. This is primarily used to track the source of funds. Since this is just for your tracking, you can move Bitcoins from one account to another just by moving a number from one column to another. No transactions are needed. (This is like when you know you owe your son $25 for allowance, and you have $200 budgeted for groceries.)

"Addresses" are used to receive Bitcoins in transactions. The coins are sent to an address. The client associates each address with an account and adds received funds to that account. This is simply done for convenience to allow people to track indirectly which address funds were sent to. But you can have any number of addresses associated with the same account.

Change comes from the way Bitcoins are spent. To spend a certain number of Bitcoins, you must pull in Bitcoins from transaction outputs to accounts you control. Note that in the spending part, it doesn't matter what address this is or what account that address is associated with. When you spend Bitcoins from a particular account, that just means you debit that account for the amount you send. It doesn't mean the funds come from addresses associated with that account. Remember, the association between addresses and accounts is for receiving only, not sending. (Like when you spend money on groceries, it's not like you have specific bills for groceries. You just have an amount budgeted.)

So when you pull in transaction outputs, you form a pile of Bitcoins big enough for the number you are trying to send. Usually, it won't be exact since you must claim an entire output. So the excess forms the 'change'.

Since there is no address associated with sending Bitcoins, there is no particular address the change should be sent to. So, to preserve anonymity, the client creates a new one just to receive the change from this transaction. Since this address isn't really associated with an account and shouldn't be used to receive any more Bitcoins (because that would senselessly tell people the same recipient got the coins as got this change) the client does not display it.

Because the client manages coins in a particular way, it doesn't make sense to try to view coins it is managing with any kind of explorer. It's specifically trying to obscure the fact that all the coins are related. Those kinds of services are intended to monitor recieved funds, not managed funds.