TL; versão curta do DR
Tags (ou rótulos, ou flags, ou qualquer que seja o seu cliente de email os chama) podem ser armazenados no servidor, mas a especificação IMAP define como opcional . Para o Thunderbird, se o servidor não permitir tags, ele será armazenado em um arquivo local.
Como as tags são definidas no IMAP
Message State Information:
Through the use of flags defined in the IMAP4 protocol, clients can keep track of message state: for example, whether or not the message has been read, replied to, or deleted.
These flags are stored on the server, so different clients accessing the same mailbox at different times can detect state changes made by other clients. (...) The IMAP4 protocol supports both pre-defined system flags and client-defined keywords. System flags indicate state information such as whether a message has been read.
Keywords, which are not supported by all IMAP servers, allow messages to be given one or more tags whose meaning is up to the client. IMAP keywords should not be confused with proprietary labels of web-based e-mail services which are sometimes translated into IMAP folders by the corresponding proprietary servers.
fonte: Wikipedia
Como o Thunderbird lida com tags IMAP
Thunderbird tries to store tags on the server using IMAP keywords. If the IMAP server doesn't support that it will store lags locally in the .msf file for the folder. That means that another PC can not see the labels.
A quick and dirty way to test where tags are stored would be to exit Thunderbird and delete the .msf file, and see if the tags disappeared. A more sophisticated way is to log into the IMAP account and to check whether the PERMANENTFLAGS server response to the SELECT command contains * (see RFC 3501).This page explains how to manually connect to an IMAP server.
Thunderbird 1.5.x uses Labels instead of tags but stores them in the same way.
For sharing tags with another PC (or Thunderbird using a different profile) you need to have defined the same tags to see them. Thunderbird appears to have hard coded support for five tags that mimic the old labels. If you use one of those tags on another PC and delete those five tags on your PC you can still see the tags in the remote folder though they will not be colored. It will display the tags in the folder listing but won't list them in the expanded header when you read the message.
Fonte: MozillaZine