To all:

I'm able to see the label on both laptop and phone by creating a receive request in bitcoin-qt with something written in the "message" field. When I scan the resulting QR code with mycelium on my phone, it labels the transaction with that message. I guess that's all transferred through extra fields in the QR code, and not part of the address itself, so that's why it can't be seen on a block explorer. Thanks!