Vamos usar o Windows XP para compartilhar sua conexão ! Primeiro você deve certificar-se que a sua rede esteja funcionando sem problemas: verifique placa de rede, cabos etc... No caso do Windows XP, você não vai precisar copiar algum programa "externo" pois o próprio Windows XP traz este software: o ICS (Internet Conection Sharing).

Você pode simplesmente usar o "Assistente de configuração de rede" ou faça o seguinte: vá em Painel de Controle > Conexões de rede > dê um duplo-clique com o botão direito do mouse sobre a conexão que deseja compartilhar. Abrirá uma tela parecida com a seguir:
 

No Menu, selecione "Tarefas de Rede" e em seguida em "Alterar as configurações desta conexão. Na guia "Avançado", selecione "Permitir que outros usuários da rede se conectem pela conexão deste computador à Internet" como na tela a seguir:
 

No caso de uma conexão Dial-Up, selecione se você deseja que a conexão seja estabelecida automaticamente quando um outro computador da sua rede tentar acessar recurso externos.Para isso, marque a opção "Estabelecer uma conexão Dial-Up sempre que um computador de rede tentar acessar a Internet." Quando a configuração for feita, o adaptador conectado à sua rede recebe uma nova configuração de endereço IP estático. 
 
IMPORTANTE: As conexões TCP/IP existentes que possui compartilhamento de conexão com a Internet, são perdidas e você precisará refazê-las.
 
Para testar sua conexão de rede e com a internet, vá a cada uma das estações de rede e e execute o "Assistente para configuração de rede a partir do CD do Windows XP" desses computadores. Depois disso certifique-se que todas as estações da rede estão compartilhando arquivos entre eles e se cada computador possui acesso a endereço da web. Depois de tudo ativado e configurado, certifique-se que todos os computadores estão comunicando entre si e se estão tendo acesso à Internet.

O compartilhamento de conexão deve ser usado em uma rede em que o computador host ICS controle a comunicação entre os computadores e à Internet.
 
Dicas rápidas:
 
Compartilhar uma conexão da Internet significa que a estação que está executando a tarefa pode ser encontrada por usuários mal intencionados e há riscos de sua rede seje atacada. É altamente recomendável que se utilize Firewall e evite compartilhar seus arquivos mais importantes: um ótimo firewall freeware é o ZoneAlarm - mas se dispor de um software pago, uma boa pedida é o Norton Personal Firewall.