Olá a todos,
Para o bom uso dessa dica, espero que você saiba determinar o IP, DNS, gateway e sub-net mask na sua placa de rede. O objetivo é apenas compartilhar com sucesso a 
Internet, por isso não explicarei o que cada comando faz. Fica para a próxima.
Característica da rede
-  Um ponto de internet (IP-fixo na eth0);
-  Um servidor Linux Kernel 2.6.x ( Fedora Core 4)
Clientes:
-  Três PCs - dois Windows Xp, um Windows  Xp e um Fedora Core 2;
-  Um laptop - Windows XP.
OBS: Para mostrar que funciona em qualquer distribuição, testei como servidor alguns live-CDs, como 
Kurumin, 
Mandrake e 
SuSE, em um computador de terceiro realizei com sucesso num 
Slackware 10.1 com kernel 2.6.11 e todas as supracitadas distros funcionaram como cliente.
Por fim:
-  Um hub/switch - apenas para servir de entreposto na estrutura da rede.
Configuração
No servidor:
A placa onde está plugado o cabo da internet você não mexe e na placa onde vai o cabo para a rede interna - conexão com o hub/switch (dois ou mais PCs) ou se é uma rede ponto-a-ponto (dois PCs) - fiz da seguinte forma:
ip      192.168.0.1
subnet  255.255.255.0
Nos PCs clientes:
ip       192.168.0.X
subnet   255.255.255.0
Gateway  192.168.0.1
O "X" fica ao seu critério desde que não seja 0 ou maior do que  199.
Enquanto que o gateway é o IP da placa do servidor conectada a rede.
DNS, essa parte é critica, você precisa descobrir qual o DNS do seu 
provedor de internet, geralmente ele está informado na placa conectada 
a internet. Para saber basta abrir o arquivo 
/etc/resolv.conf. O primeiro conjunto de números que você ver no resolv.conf você joga no DNS primário e assim sucessivamente.
Feito isso basta digitar os seguintes comando no shell do servidor 
Linux como root:
# iptables -F
# iptables -F INPUT
# iptables -F OUTPUT
# iptables -F POSTROUTING -t nat
# iptables -F PREROUTING -t nat
# iptables -P FORWARD ACCEPT
# iptables -t nat -A POSTROUTING -j MASQUERADE
# sysctl -w net.ipv4.ip_forward=1
Está pronto seu compartilhamento!
Observe que na penúltima linha "iptables -t nat -A POSTROUTING -j MASQUERADE" você não tem qualquer alusão a um tipo de conexão, seja ela ppp0 ou eth0, dessa forma a configuração fica o mais possível e  genérica. Testei no laptop desse jeito na casa de um vizinho que usa 
Velox, que é a internet banda larga da Telemar via ADSL e funcionou do mesmo jeito já no caso de discada não testei. Não tinha um modenzinho sequer.... :(
Esse conjunto de comandos que você digitou no servidor você terá que digitar toda vez que o servidor for reiniciado. Eu tentei jogar isso em um script de boot mas não consegui sucesso.