How does WalletExplorer know which wallets belong to whom? I do understand that for two addresses to be on the same side of a transaction, they must be within the same wallet, since one private key is used to sign a transaction.

However, how is WalletExplorer able to put a name to some of these wallets?
What walletexplorer does is called address clustering. When you spend bitcoins, your wallet will take input from several txouts belonging to several addresses depending on amount to be spend. So walletexplorer works on a simple heuristic:


If two addresses appear as inputs in any given transaction, they belong to same user


More detail about this method can be seen in this paper by Reid and Harrigan. Of course, this method will fail in case of mixers and coinjoin transactions. There are advanced ways to even detect transaction that go through mixers, but I don't think wallet explorer does that 

To find name of wallets it can scrap forums like bitcointalk, some addresses are tagged publicly in blockchain.info, also it can has bots trade on major exchanges to get their addresses.