So, I'm wondering how I can tell if programs are making outbound connections, and if so, where the connections are going to.

It's a poor comparison, but in windows, everytime a connection is attempted, zonealarm firewall told me "such-and-such is trying to reach <ip>, allow or disallow?". I liked that feature; I felt in control.

I know I have programs that are accessing the net without my direct intervention (ex: popularity-contest, sshd (when it initates a connection), non-free binary only programs, etc), so how can I monitor which ones connected when?

PS I know I can monitor sshd via auth.log.

I personally haven't ever come across a ZoneAlarm equivalent for Linux, however Ethereal and <netstat -lnp> are good places to start if you are curious as to what's coming in and out of your system. Firestarter is also quite useful, but concentrates on inbound connections. Otherwise, on a separate, old box you could always install Smoothwall or IPCop.

Sniffers are the basic tools for monitoring outgoing (or incoming) net connections. The basic no-frills option is the standard 'tcpdump' (many other sniffers have options to load or save data in 'tcpdump format') which requires some old-style unix command line savvy. Ethereal is the best known and widely used, it has a GUI, but you still have to know what you're doing; it is quite sophisticated and complex. Netstat shows active connections, but you would have to run it while the program was talking to the world, and some connections can be brief. Snort runs as a daemon and can be told to look for and log various things, but it also requires skill to use properly.