How do wallet-sites generate large numbers of Bitcoin addresses?
At Justcoin.com, we've used a few different methods over the years:


Generate addresses using bitcoind, now called bitcoin core, when we need them. To avoid key loss in the case of storage failure, we use a large key pool. The command is simply getnewaddress.
Hierarchical deterministic wallets are much better and we use these for an increasing number of things. When using these for hot wallets, we import new private keys into our hot wallet before its ever used. That way we can still spend its inputs from bitcoind.