There are different possible approaches.
Most current wallet software uses HD wallets, where keys and addresses are generated as needed from a master seed. In this case, a change address would likely not be generated until it is needed. A new address would be generated for each new transaction as this is better for privacy.
With Bitcoin Core, prior to the implementation of HD wallets, the default was to pre-generate 100 addresses and store the keys in wallet.dat as a "keypool". Change addresses would then be taken from the keypool, again using a new one for each transaction. This was done so that each time you backed up wallet.dat, you would also be able to protect the keys for transactions you hadn't yet made. Without this behavior, you would have to back up wallet.dat immediately after every new transaction - and if your disk crashed between the transaction and the backup, you would lose coins.
Some wallet software used to only generate one address and use it for all incoming transactions as well as change. This is no longer common, though some wallets still provide it as an option.