How do wallet-sites generate large numbers of Bitcoin addresses? How do online Bitcoin wallet sites work? How can they have thousands of addresses laying around, or do they create them on the fly?  What sort of software is used to create all those Bitcoin addresses?  The reason I ask, is that I'm toying with an idea for a website that would require per-user Bitcoin addresses for payment.
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.