Faits: A. A._ et dame B._ se sont mariés en 1995. Deux enfants sont issus de leur union: C._, née en 1996 et D._, né en 1999. B. Par jugement du 15 décembre 2009, le Tribunal civil de l'arrondissement de l'Est vaudois a prononcé le divorce des époux, attribué l'autorité parentale et la garde des enfants à la mère et réglé le droit de visite du père. A._ a recouru contre ce jugement auprès de la Chambre des recours du Tribunal cantonal vaudois. Dans ses dernières conclusions, il admettait l'attribution de la garde à la mère, mais demandait que l'autorité parentale soit conjointe. Par arrêt du 9 février 2010, l'autorité saisie a rejeté le recours. Elle a relevé que l'autorité parentale conjointe nécessitait une requête commune, qui faisait défaut en l'espèce. C. Par écriture du 1er juin 2010, A._ forme un recours au Tribunal fédéral. Il conclut au prononcé de l'autorité parentale conjointe. Il requiert en outre le bénéfice de l'assistance judiciaire pour la procédure fédérale. La cour cantonale se réfère aux considérants de son arrêt. L'intimée propose principalement le rejet du recours, voire son irrecevabilité. Elle demande subsidiairement le renvoi de la cause pour complément d'instruction et nouvelle décision. Elle sollicite également le bénéfice de l'assistance judiciaire pour la procédure fédérale.