How to install a language package in Texmaker on Ubuntu 12.04?

Have you tried this in a terminal?

$ sudo apt-cache search texlive french
 texlive-doc-fr - TeX Live: French documentation
 texlive-lang-french - TeX Live: French

$sudo apt-get install texlive-lang-french

This example should work in a well installed TeX Live:

documentclass[french,11pt]{article}
usepackage{babel}
usepackage[utf8]{inputenc}
begin{document}
section*{L'histoire de la France au Moyen Âge}
L'histoire de la France au Moyen Âge se 
caractérise par plusieurs périodes et événements 
marquants durant dix siècles: de Clovis à 
Charles VIII, en passant par la fin de la 
Gaule romaine quand elle se détache de 
l'Empire romain, la guerre de Cent Ans, 
l'unification de la Gaule qui, au terme d'une
longue genèse, deviendra un État spécifique, 
le Royaume de France. Celui-ci apportera l'essor
 du christianisme, des campagnes, de la 
 population française, la renaissance 
 urbaine accompagnée par l'apparition 
 et l'affirmation des universités, la 
 formation de la langue française et 
 le développement du commerce (foires 
 et marchés).
end{document}