Use Squid (see
http://www.squid-cache.org) on a Linux server. This server can be your gateway (if bi- or tri-homed) and do the firewalling, otherwise you have to configure your FW to let queries go to the internet only if they come from your Squid server. If Squid isi on your gateway, make sure it cannot be used from the untrusted side.