See also http://www.candelatech.com/~greear/vlan.html  Candelatech's page.
1. What are vlans ?
Vlans are a way to split up a layer2 broadcasting domain, by allowing multiple broadcast domains that each have a number (1-4096), and that can contain individual hosts, which are then not able to talk to eachother without passing through another device first (such as a firewall). VLANs allow you to create multiple separated networks with only a single switch.
In order to make a linux host capable of being present on multiple vlans (so that it can forward traffic to it) on a single interface, you will need the vlan support. All packets come in over a single interface, but they are delivered to "vlan-subinterfaces" where they can be firewalled, routed, or anything else.
In a vlan-capable network there are 2 types of connections : "access" connections and "trunk" connections. Simply put, an access connection looks like a normal connection to an ethernet switch, only that switch will only forward your packets within the same vlan, so they will not be able to reach ports that are in a different vlan. "Trunk" ports can communicate with multiple vlans, but you need to send special packets that contain both the packet and an indication in what vlan they are to be forwarded. On these links you use the linux vlan support to create virtual interfaces that are in different vlans.
2. Two standards
There are 2 ways of doing vlans in networks : 802.1q and ISL. ISL came first, and was a cisco proprietary protocol that they built into their switches while the dot1Q standard was still in development. Only cisco switches support this protocol, and linux does not. 802.1q is a standard specifying how it can be implemented, what the packet format is, ... You can find it here http://www.cisco.com/warp/public/473/741_4.html .
Not covered here. See http://www.cisco.com/warp/public/473/741_4.html 
Normally you will find in the ethernet 802.3 header the following for a vlan packet :
|Packet type||Preamble||Start frame delimiter||Destination MAC address||Source MAC address||dot1q identifier||tag type (4 bits)||vlan ID (12 bits)||packet type field||data||padding||FCS|
|Normal ethernet tcp packet||1010101010101010101 (62 alternating bits)||00:10:C6:C0:61:CD||00:13:CE:47:06:86||not present||not present||not present||0x0800||<insert ip packet here>||<insert padding if packet too small||<checksum>|
|VLAN packet||1010101010101010101 (62 alternating bits)||00:10:C6:C0:61:CD||00:13:CE:47:06:86||0x8100||QOS bits||VLAN ID||0x800||<insert ip packet here>||<insert padding if packet too small||<checksum>|
So VLAN packets can be identified by their TYPE field, which is set to 0x8100. If the packet is to be received, the VLAN tag is to be stripped of the packet, and a second TYPE field will have to be interpreted. It is possible to insert multiple VLAN tags, although this is not supported on linux, nor is it supported on many devices. (Search cisco dot1q tunnel implementation).
3. How does it work on a protocol level ?
For VLAN support a special type of ethernet packet was created. It basically has an extra header that allows you to specify what vlan the packet is in. And
-> for access ports, the switch will add (or overwrite) this value on any incoming packet before forwarding
-> for trunk ports, the value is supposed to be present. If it is not, the value of the "native vlan" will be added.
So basically you have an ethernet frame containing tcp data :
The switch will transform this packet into this on access ports :
and on trunk ports you simply get the full packet.
3. How does it work in the linux kernel for administration
3.1 The vconfig tool
Using the vconfig tool you can add a VLAN subinterface. Say you have configured the switch eth1 is connected to to send packets in the vlans 810 and 820. Then you can do
vconfig add eth0 810 vconfig add eth0 820
And two new interfaces will be defined "eth0.810" and "eth0.820" which behave exactly like ordinary interfaces, and it is as if they are connected to different networks. So you should use different IP subnets on them.
You could also run DHCP on only one of these interfaces, and have a number of switchports which support DHCP and some which should not.
To enable routing between the different vlans, do :
echo 1 > /proc/sys/net/ipv4/ip_forward
After which the devices on the network will be able to talk to eachother, after you set a route on them
(on the client devices in an access port :) route add <network on other vlan> netmask <the netmask of the network> gw <the ip of the vlan router on the correct vlan>
After you do this on 2 devices, they should be able to ping eachother. (Why two ? The packets need to get from A->B and from B->A, so 2 routes are needed before ping will work)
4. The kernel implementation
4.1 Packet reception
When a hardware driver receives a packet, it will receive the packet into a sk_buff structure (defined in include/linux/sk_buff.h), and it will set the ->dev member to it's own interface,
after which the packet is passed to the netif_rx ( net/core/dev.c ) or receive_skb ( net/core/dev.c). So basically receiving a packet works like this :
struct sk_buff * skb; skb = dev_alloc_skb(); /* fill in some data in the skb */ skb->dev = my interface struct netif_rx(skb);
When an interface receives a VLAN packet (if the interfaces have vlan acceleration) the call to netif_rx will be replaced by :
vlan_hwaccel_rx(skb, vlan_group, vlan_tag)
Which will then immediately overwrite the skb->dev to the correct subinterface and pass it on to the netif_rx routine.