Much obviously depends on what type of network traffic will pass between the 2 locations.
If your only need occasional, essentially one-way communications (from the warehouse to your main site), a dial-up connection may suffice.
If you need a morepersistant connection with traffic flowing both directions, I would suggest some sort of VPN solution. If you are already using Win2K server at your main site, you have most of the capability built-in. I would suggest upgrading the Win95 workstation to Win2K Pro to make life simpler (and more secure). Then all you need is a means for the warehouse workstations to connect to the Internet (whether DSL, ISDN, or even Cable). Your hw costs at the warehouse end (especially if using either DSL or cable) would be limited to a modem (DSL, Cable, ISDN) and a router/firewall (from a vendor such as Linksys).