How do you learn someone's username or email? They tell it to you. Actually, in Bitmessage they tell you an "address" which is a compact hash of a pubkey. Then, p2p network uses special kind of message "what's the pubkey for this address?" which allows your client to find out the pubkey.

An address looks like this: BM-orkCbppXWSqPpAxnz6jnfTZ2djb5pJKDb (this one belongs to an echo server). People who got used to Base58-encoded Bitcoin addresses will find this familiar.