802.1q gives you the power to set up VLANs by tagging your ethernet frames with a 12 bit identification number. In linux, you create a virtual network device with the vconfig tool for each VLAN you want to participate in.
This is how it works:

This is the header of a standard Ethernet packet (IEEE 802.3):
  destination address             (6 bytes)
  source address                  (6 bytes)
  protocol of encapsulated packet (2 bytes)

Source and destination address are, of course, the MAC addresses of the sender and the reciever.

The protocol field denotes what type of data the rest of the packet contains: this is 0800 (hex) for your everyday IP traffic.
In packets tagged with a 802.1q VLAN however, the protocol field is set to 8100 and four additional bytes are added to the Ethernet header:
  TCI                             (2 bytes)
  protocol of encapsulated packet (2 bytes)

Again, the protocol field tells us what protocol is expected in this packet (you will most often se 0800 - IP packets)

The TCI field is the interesting part, though. It consists of a priority and the VLAN ID (12 bits - giving us a total of 4096 IDs).

tcpdump, if not patched to recognize Q-tagged VLANs, will show something like this when a frame with a VLAN ID floats by (tcpdup -e -n):
18:33:45.764835 0:50:ba:c4:b:62 ff:ff:ff:ff:ff:ff 8100 60:
                         029a 0806 0001 0800 0604 0001 0050 bac4
                         0b62 c0a8 0003 0000 0000 0000 c0a8 0002
                         8010 f500 e43b 0000 0101 080a 0093

On the first line you see the time of reciept (I assume), the transmitters MAC address, the recievers MAC address (the broadcast address), the encapsulated protocol id (8100 - says that this is a 802.1q packet) and the size of the packet.
The first two bytes of the packet dump (029a) show the TCI field of the header: the priority is 0 and the VLAN ID is 0x29a (that is 666 in decimal).
The next tho bytes tell us that the type of packet that follows is 0806, that is ARP (used to resolve an IP address to a MAC address). Following that is the ARP packet itself.

For more information, see /usr/src/linux/include/linux/if_vlan.h and google.