How to connect to a remote CPU on a private network

I supervise the installation, configuration, and support for a network of nearly 1,000 PCs installed among 30 different locations. Each location has between 20 and 100 machines, the bulk of which control point of sale (POS) devices. The individual locations are connected to the central office via frame, but each are limited to 30 public IP addresses (due to cost saving decisions by my predecessor). There are not enough public IPs available for every CPU to have one - the POS CPUs use Netbeui to communicate with the site's server. I have a Windows Update Server in the central office, and have no trouble setting up remote CPUs that have public IP addresses. The POS CPUs all have private IPs, which is fine within that building, but I need them to communicate with the central office. I am more administrative than technical (if you didn't figure that out yet), but I'm looking for options. The POS CPUs with private IPs use a site server as a gateway. Is there a way to use the site server as a sort of bridge to addresses outside the building? Host file entries? Shareware? Any help would be appreciated.