Oddly enough, this is something many people don't think about a whole lot. In some cases, you can simply deny everything and have a few specific allow rules, resulting in a pretty tight configuration. However, you will more likely have specific blocking rules and allow most other things. This is usually based on port numbers (i.e. service) and destination, but source is also very important. Even if you only allow a few trusted IP addresses to, say, connect to your "secret" web server, an attacker can still spoof packets, and so on. You can reduce the risk by blocking IP addresses that are in "high risk" environments, such as universities, foreign countries and so on (assuming, of course, you are not terribly interested in talking to them via the Internet).
If your business is only concerned about North America, for example, it might make sense to heavily restrict access from other countries, such as Russia and China. If you are securing network sites that are not providing public network services (such as WWW sites), then you should probably restrict access from network blocks like 24.* (cablemodem providers, a favorite jumping point for attackers).
Chances are that not all of your internal machines require access to the Internet, and by blocking them you can head off problems. Machines without Internet access cannot connect to "naughty" sites, and Trojan horse software running on them cannot contact outside sites to report it is installed, or send stolen passwords.
Any machines providing services to Internet users (such as DNS, WWW, email) should be allowed access to the Internet - otherwise, they will not work. You may wish to restrict it, though. For example, the mail server should only need to reply to clients that initiate connections, and only establish connections to other mail servers (port 25). There is no need for the mail server to establish connections to machines on any other port than 25. Thus if someone were to break into your mailserver, they would only be able to attack other machines on a single port (port 25), instead of all 65,536 ports (and, of course, you would be able to quickly detect this type of behavior). Web servers should only need to answer queries to ports 80 (and 443 for secure web). Generally speaking, they do not need to establish outbound connections.
By heavily restricting the outbound access of machines, you can significantly reduce your exposure, and increase the chances of detecting a security incident.
There are many services - thousands in fact. Some of these services are so common, though, and so dangerous, that they warrant special attention. The most common problems are in what I call network infrastructure protocols - protocols that almost all networks use, such as DHCP, DNS, SNMP, LPR, NFS, and SMB, which provide basic network management, or services such as file and print sharing. Generally speaking, these do not need to be shared out across the Internet, and if remote users do need access to them (as with file and print sharing) they should be tunneled through a VPN (such as IPSec) and not allowed to go out in the clear.
23/tcp - telnet, cleartext authentication and sessions, should not be used (replace with SSH).
37/tcp and udp - time, use ntp (Network Time Protocol) instead.
67/tcp and udp - bootp server, should only be used locally.
68/tcp and udp - bootp client, should only be used locally.
69/tcp and udp - tftp (Trivial FTP), should only be used locally.
79/tcp - finger, should only be used locally.
110 and 111/tcp and udp - POP2 and POP3, if remote users need access use SSL wrapped POP or VPN.
143/tcp and udp - IMAP, if remote users need access use SSL wrapped POP or VPN.
161/udp - SNMP, attackers love this protocol.
162/udp - SNMP-trap, attackers love this protocol.
177/tcp and udp - xdmcp (X Display Manager Control Protocol, restrict access or VPN.
389/tcp - LDAP, restrict access or VPN.
512, 513 and 514/udp and tcp - various remote services and logging, restrict access or VPN.
1812/tcp and udp - Radius, restrict access or VPN.
And the list goes on and on. The decision tree should look like this:
Can we firewall it completely? If yes do so.
Can we restrict access to it to people via a VPN only (i.e. IPSec)? If yes do so.
Can we firewall it restrictively (i.e. to "trusted hosts")? If yes do so.
Can we restrict access to it from "risky" sources (i.e. Canadian colleges, China, the USA)? If yes do so.
The trick is to configure the firewall in the most restrictive way possible, while still allowing the network to be usable.