VLAN tags are only used on trunk links. Most hosts cannot understand VLAN tags since they increase the frame size. Hosts that do understand VLAN tags may be connected with a trunk link instead of an access link.
The definition of a native VLAN frame on a trunk is that it _does not_ contain a VLAN tag. All the frames in any other VLANs on the trunk _do_ contain VLAN tags. Depending on the switch model and software version, each trunk link may have a different VLAN as the native VLAN, but both ends of a trunk should agree on which VLAN is the native VLAN, otherwise various problems may arise, such as traffic being sent to the wrong VLAN or incorrectly bridging two different VLANs into one broadcast domain.