I searched for a Ethereum address into etherscan.io and it showed me that it was a Poloniex address. That address was the receiving address of a wallet I created on Poloniex. How did etherscan know it belonged to Poloniex?
As @RobHitchens states, Etherscan maintains an address book. To populate the address book, Etherscan can do some sleuthing to figure things out (after all, Ethereum is only pseudonymous) and they have ways to let people comment on addresses. They probably also accept e-mailed linking of addresses to entities.
As for a newly generated address, Poloniex may use a hierarchical deterministic wallet system which allows them to generate families of addresses from a single master seed. BIP 32 allows sharing a secret that allows the child account addresses to also be deterministically known without knowing the corresponding private key generation secret. If Poloniex uses this mechanism and has shared the secret with Etherscan, then Etherscan can figure out that a newly seen address belongs to Poloniex. This is speculation on my part, however, as to whether this is what Etherscan and Poloniex have done.