Собственно, установка шлюза на базе Ubuntu-Server занимает не больше 10-15 минут. Что я и проделал не так давно.

1. Устанавливаем систему (я ставил ubuntu-8.10-server-i386.iso);
2. У меня подключение по локальной сети с использованием PPPoE. Для этого просто-напросто было запущено sudo pppoeconf и даны ответы на вопросы. По окончании работы pppoeconf соединение было установлено, о чем свидетельствовал положительный вывод на команду ifconfig ppp03. На установленной машине интернет появился. Теперь надо добавить включить все репозитарии в /etc/apt/source.list и выполнить sudo apt-get update;
3. Для доступа с других машин вашей локальной сети необходимо поставить всего лишь навсего два малюсеньких пакета: dnsmasq — чтобы переправлслись ваши DNS-запросы и ipmasq — собственно для NAT'a;
4. На машинках локальной сети получаем IP по DHCP от dnsmasq либо прописываем шлюз по умолчанию ручками;

Да поможет Вам данная инструкция! Ура! Далее про добавление squid ко всему этому хозяйству.