Q:

How do a firewall's rules for individual programs work?

I kind of know that how a firewall's rules for IP/port work, but I have no idea how a firewall deals with individual programs.
In other words, how does the firewall know a program wants to access the Internet and stop it?

A:

Application filtering firewalls are hooked into the operating system at the kernel level and aware of any file access. That file access awareness includes network sockets.
For a visual demonstration of this on:

Linux, use lsof -i
MacOS, use lsof -i
Windows, use Process Explorer

The firewall is aware of the requesting process and associated network information (port, state, address, etc.) just as those applications above are, but it also has the ability to modify, prevent, or close connections.

A:

Jeff Farland's answer is absolutely correct so if you're looking for the short, quick answer, that in my opinion is it.
However, I like to know exact details (like how exactly is it done) because I'm like that and this is a bit too long for a comment, so, I'll focus on Windows software-based firewalls, since that's where you are most likely to find commercial software application firewalls. A lot of these links are direct to developer documentation and get quite technical quite quickly, so if that's not you the reader's thing, I apologise, hopefully it's a useful introduction to someone though.
Basically, Windows actually has a whole set of OS functionality that allows you to filter out, deny requests, inject requests etc. The most easy to find documentation on the subject starts with the file filtering manager used by many antivirus products. There's a brilliant diagram in there showing you exactly how each request works. Essentually, there's a driver stack, part of which includes a series of minifilters which are sorted by priority order and applied to the request. This is probably what your average antivirus does and is why many antivirus products can't be installed simultaneously; they interfere with each other. Although this is for file based activity, so:
For firewalls, going forward it makes the most sense to talk about the Windows Filtering Platform, one of the many security changes that came about in Vista. A direct link of interest is the part explaining the many ways application level firewalls could be implemented in previous versions of windows. Basically put, it was very complicated and again why two firewalls might not just cause collisions, but actual system instability. Aside from that, a lot of vendors were (are) writing firewalls.
The really simple way to explain WPF is this: you have two options available to you. The kernel (Windows itself) provides you with a certain set of default filters you can apply (which are fairly flexible looking at the samples). If you want to do anything more, you need to build a callout driver which is essentially the same idea as the minifilters above. In callout driver mode, you can inspect the contents of the packet and do whatever you want to to it based on that information.
The reason for introducing this change is the introduction of Kernel Patch Protection, a mechanism to prevent drivers modifying the core of Windows in ways you do not want. Coupled with that, it is entirely possible to do a lot of filtering without even writing drivers, see this sample code. And if you're interested in making one, or just wondering where I found all this, here's the steps to learn about it building a WFP based product page from MSDN.
So, basically, what Jeff said, really. Obviously Linux and Mac OS X are different again; I've tried to concentrate on the OS with which most people will have used a product like this.
By the way; Jeff mentioned Process Explorer. The sysinternals utilities use these and other filtering APIs to give you the information you see there these days.

A:

Backing up a step here, and writing between the posts - there are a number of different types of firewalls out there.  The capabilities built into the firewall and the location of the firewall within the network have a lot to do with what the firewall can do.  Whether or not a firewall can even detect the program transmitting the data has a lot to do with these factors.
First, a definition - a firewall can (really loosely) be defined as something that watches and filters traffic on a network.  It can be:

part of a network device - built into a router or a switch
a standalone device that does nothing but filter traffic
a piece of software installed on a computer system like a workstation or labtop

It can be located virtually anywhere it can be plugged in, but the general idea is to put it between stuff you want to protect and stuff you don't trust.
From there, there are dizzying number of types of firewalls out there and how they work has a huge influence on what they can do.  Here's some examples of variations:

network layer watched - application, session and network layer are the big ones.  I'm sure that if one looks hard enough, one can find firewalls that operate on other layers, but those are the big ones.
proxy vs. stateful - if it's a proxy type firewall all it can do is compare this message to a set of rules for wrong vs. right for the given target.  If it's stateful, it can build up a set of rules based on what's come before.  

Combining even these three things (where it's located, what layer of networking it can watch, and whether its proxy or stateful) can produce a wide variation in what the firewall can do.
In general, all firewalls have a set of rules for good vs. bad behavior.  I would suspect that unless you are talking about an application level firewall running on the protected computer system with non-firewall-like features - that the firewall can not spot a program and stop it from running.  I've never heard of a firewall that can, for example, see that I'm using Microsoft Word and stop me from using it.
What an application firewall can do, however, is block application level traffic, which will render some applications useless - for example, try using a web browser without access to the Internet.  Usually when a firewall claims to block applications, it means applications in the sense of network transmissions.  In that sense, the HTTP traffic produced by my web browser is considered the application.
Rules can range from things that are really simple - i.e. "don't allow incoming HTTP GET requests" to something complicated, like diagnosing a series of requests that shows the handle of some sort of attack.  The key is, about all a firewall has to go on is where the message seemed to come from, where it's headed, and what's in it.
One last caveat - encryption methods will change what a firewall can and can't do.  If the firewall terminates the SSL/TLS session, then it can be capable of doing application level processing, even on SSL transmissions - but if the SSL/TLS or other encrypted pathway is from client to server, then the best that the firewall can do is make sure that the SSL is well formed.

