Encontrei alguns cursos on-line sobre Linux que chegam até a preparar para as provas LPI aplicadas pela LPI Brasil.
Existem cursos gratuitos, e alguns pagos com preços bem acessíveis.
Hoje também existem cursos de pós-graduação em software livre, com custos de mercado.

Em inglês:

LearnLinux contém vários cursos nesta página.
A IBM está reunindo material de preparação para os exames LPI 101, 102 e LPI 201, 202 neste site aqui.

A partir de outubro 2007, a IBM oferece cursos LPI 301 também neste site aqui .

A IBM requer cadastramento gratuito para acessar os conteúdos dos cursos 101, 102, 201, 202, 301.

Mais material preparatório para exames certificação LPI pela IBM pode ser encontrado a partir de links nesta página aqui . O acesso exige registro gratuito.

Guia Rute.
The Linux Documentation Project.

Em português:

O site E-cursos on-line tem cursos abertos e fechados de vários níveis. Existe um de nível introdutório gratuito que você pode fazer para conhecer o sistema de ensino à distância.
Mesmo os cursos pagos têm preços bem acessíveis, muito mais em conta do que cursos presenciais.
O site é uma iniciativa da Hitec Informática, que já promove cursos presenciais e aplica provas de certificação há vários anos.
Já cursei vários dos treinamentos presenciais deles e são muito bons.
O site Guia Foca Linux reúne uma das melhores documentações de treinamento sobre Linux. Separado em três níveis de conhecimento.
The Linux Documentation Project Brasil.
A seção de documentação do Debian GNU / Linux possui muitos documentos e links externos também.
O Centro de Difusão de Tecnologia e Conhecimento disponibiliza vários cursos on-line gratuitos, com monitores. Como depende do número de monitores disponíveis, pode haver uma grande fila de espera. Inscreva-se e aguarde a chamada. Para ganhar certificado, somente após prestar monitoria em ao menos um curso. Leia o regulamento. Quanto mais participarem, maior será o número de monitores e maior o número de turmas.

O site Certificação Linux promove cursos on-line multimídia preparatórios para as provas de certificação LPI.

A Novintec oferece cursos presenciais preparatórios para as provas de certificação LPI, diretamente e através de parceiros, em algumas cidades.

A IBM oferece cursos presenciais preparatórios níveis 101 e 102 para as provas de certificação Linux LPI.

A comunidade LinuxBrasil oferece alguns cursos gratuitos on-line sobre Linux e alguns dos softwares livres, como BrOffice e bancos de dados.

A empresa TreinaLinux oferece várias vídeo aulas, algumas gratuitas, de treinamento em GNU / Linux, software livre e hardware. Os gratuitos são para nível iniciante.

A empresa E-Help oferece vários cursos on-line e presenciais, sendo alguns on-line gratuitos.

Se você souber de mais algum site, por gentileza, avise ou já faça log in no quadro ao lado e coloque seu comentário abaixo.