Du musst auf jeden Fall zwischen der Signatur eines anderen öffentlichen Schlüssels und der Vertrauens-Info unterscheiden.
Um deine ursprüngliche Frage zu beantworten: Die Vertrauensinfo wird nicht im öffentlichen Schlüssel gespeichert, sondern jedenfalls bei GnuPG in der Datei .gnupg/trustdb.gpg. Siehe dazu hier: https://www.gnupg.org/gph/de/manual/x420.html
Das Vertrauensmaß eines Schlüssels ist etwas, das Sie alleine dem Schlüssel zuordnen, und es wird als private Information betrachtet. Es wird nicht mit dem Schlüssel verpackt, wenn dieser exportiert wird; es wird sogar getrennt von Ihren Schlüsselbunden in einer gesonderten Trustdatenbank (trustdb.gpg) gespeichert.
Wenn du einen anderen Schlüssel signierst, bedeutet dies, dass du an den anderen Schlüssel eine Signatur dran hängst. Den geänderten anderen Schlüssel kannst du dann auf einen öffentlichen Schlüsselserver hochladen. Diese Schlüsselserver arbeiten so, dass sie es jedem erlauben einen beliebigen öffentlichen Schlüssel zu ergänzen. Dieser ganze Prozess hat wie oben dargelegt jedoch nichts mit dem Vertrauen zu tun. Andere Personen müssen nun selbst interpretieren was es bedeutet, dass du einen anderen Schlüssel signiert hast.
Um es anderen Personen leichter zu machen wie deine Signatur verstanden werden soll, kannst du der Signatur noch einen "Hinweis" mitgeben. Bei meinem Schlüssel sieht es zum Beispiel so aus: https://pgp.mit.edu/pks/lookup?op=vindex&search=0xE72581B1FE9F104C
Teilweise steht vor den einzelnen Signaturen "sig" und teilweise "sig3". Diese Zahl (1, 2 oder 3) stellt einen Hinweis da. Was der genau bedeutet, ist jedoch nicht genau definiert. Je höher desto besser. Diese Information wird mit in den öffentlichen Schlüssel gespeichert. Hat jedoch wie oben geschrieben keine unmittelbare und unbedingte Auswirkung auf das Vertrauen.
Ich weiß, es ist etwas off-Topic, aber ich persönlich halte nicht viel vom Web of Trust. Ich folge eher Werner Koch (Der Mensch hinter GnuPG, quelle: https://www.gnupg.org/blog/20150911-gnupg-this-summer.html zweiter Absatz) und finde das Konzept von TOFU besser geeignet als das Web of Trust.