Под прокси-сервером в обычно подразумевается просто HTTP-Proxy. Его основная задача схожа с NAT, но ограничивается исключительно протоколом HTTP (обычно умеет еще и FTP). Суть такова: в данном случае клиент приватной сети должен быть настроен для работы с прокси. После настройки (указания InternetExplorer'у адреса прокси) клиент свои запросы шлет не непосредсвенно серверу, с которым хочет связаться, а прокси-серверу, т.е. он явно просит прокси-сервер скачать для него такую-то страничку или файлик. Прокси-сервер самостоятельно скачивает страничку и отдает ее клиенту... при этом копию странички он может временно сохранить у себя, для того, чтобы отдать ее не скачивая из интернета в том случае, если она снова понадобится...

Proxy, естественно, бывают не только для протокола HTTP, и работать могут совершенно по разному. Если не ошибаюсь, то Proxy переводится с компьютерного на русский как "посредник". NAT-Server тоже является прокси, только для протокола IP, а не HTTP.