For example if I send Bob 1 BTC as a gift, I would like to add "gift to Bob" in my list of transactions so I can recall later on what specific transactions were all about.
Oh crap, I misread this the first time around. So I'm assuming there really isn't a wallet that lets you send a note to someone on the receiving end of a transaction, right?
No, the label/note is only stored on your device. If you only backup your seed/mnemonic words, the label/note will be gone.