Modern computers typically exchange data by breaking it up to network frames. These frames are called "packets" in TCP/IP, the most commonly used network protocol. Firewalls inspect each packet and decide whether it should be allowed to pass the firewall and continue travelling towards its destination, or discarded. Common ways of filtering packets are according to the source/destination address or according to the source/destination port.
But in some cases this information is not enough. The administrator of the firewall might want to allow packets to pass the firewall according to the context of the connection, and not just the individual packet characteristics. Therefore, a packet belonging to an existing connection, aimed at port 22 (the Secure Shell port) should be allowed to pass the firewall, but a packet that does not belong to any existing connection must be dropped.
With the traditional stateless firewalls, this was a problem, since the firewall had no way of knowing which packets belonged to existing connections and which didn't. Stateful firewalls solve this problem by monitoring network connections and matching any packets they inspect to existing or new connections. Therefore, they offer more fine grained control over network traffic.
Examples of stateful firewalls: