Well first of all what OS are you running on the Server that provides internet access?

What hardware routers do you have in place?

Are there are firewalls on the OS/hardware?

Depending on what you have in place already, there might be a facility to allow VPNs through routing and remote access for example on Windows 2003 Server.