In computing, a stateless firewall is a firewall that treats each network frame (or packet) in isolation. Such a firewall has no way of knowing if any given packet is part of an existing connection, is trying to establish a new connection, or is just a rogue packet.
Before the advent of stateful firewalls, this behavior was normal. Modern firewalls are connection-aware (or state-aware), affording network administrators finer-grained control of network traffic.
The classic example is the File Transfer Protocol, because by design it opens new connections to random ports.
Suppose you are the firewall of Acme Inc, protecting the company from unauthorized traffic from the Internet. You notice a TCP packet coming from some host across the globe, destined for a machine of your internal network, TCP port number 4970. This port number does not correspond to any well-known service that your protected network is supposed to provide (like Web, FTP or SSH), so you discard the packet. Congratulations, you just broke a legitimate FTP connection!
FTP, among other protocols, needs to be able to open connections to arbitrary high ports to function properly. Since the firewall has no way of knowing that the packet destined to the protected network, to some host's port 4970, is part of a legitimate FTP session, it will drop the packet. Stateful firewalls solve this problem, by maintaining a table of open connections and intelligently associating new connection requests with existing, legitimate connections.