Sachverhalt: A. In der Zeit von Oktober 1992 bis ca. 1998/1999 fasste X._ sein damals 4 bis 10 Jahre altes Patenkind A._ wiederholt über und unter den Kleidern im Intimbereich an. Überdies weckte er das Mädchen, wenn es bei ihm und seiner Ehefrau übernachtete, in der Nacht auf, brachte es in die Küche und masturbierte dort bei entblösstem Geschlechtsteil, während er dem Mädchen seinen Finger in den After und in die Scheide einführte. Er forderte dieses überdies auf, seinen Penis zu berühren und zu küssen. Anlässlich eines Vorfalls führte er seinen Finger ruckartig und für das Kind schmerzhaft in dessen After ein. Als es deshalb den Raum verlassen wollte, hielt er es zurück und sagte ihm, es dürfe niemandem etwas sagen, ansonsten er seiner Ehefrau - der Tante des Kindes - weh tun müsste. In der Zeit von Oktober 1992 bis ca. 1998/1999 bzw. von ca. 1995 bis ca. 1998/1999 berührte X._ über den Kleidern gezielt die Geschlechtsteile seiner knapp 5 bis 12 bzw. 5 bis 9 Jahre alten Neffen B._ und C._, während er mit ihnen spielte und herumtollte. B. Das Regionalgericht Berner Jura-Seeland sprach X._ am 21. Juli 2011 schuldig der sexuellen Handlungen mit Kindern, begangen in der Zeit von ca. Oktober 1992 bis ca. 1998/1999 zum Nachteil von A._ und B._ sowie, begangen in der Zeit von ca. 1995 bis ca. 1998/1999, zum Nachteil von C._. Es verurteilte ihn zu einer bedingt vollziehbaren Freiheitsstrafe von 18 Monaten bei einer Probezeit von zwei Jahren. Es verpflichtete X._ zur Zahlung einer Genugtuung von Fr. 9'000.-- an die Privatklägerin A._. Deren Schadenersatzforderung hiess es dem Grundsatz nach gut und verwies sie bezüglich der Höhe auf den Zivilweg. Die Generalstaatsanwaltschaft des Kantons Bern legte, beschränkt auf den Sanktionspunkt, Berufung ein. Das Obergericht des Kantons Bern stellte mit Urteil vom 9. März 2012 die Rechtskraft des erstinstanzlichen Schuldspruchs und des Zivilpunkts fest. Es erhöhte die Freiheitsstrafe auf 30 Monate und setzte den unbedingt zu vollziehenden Teil auf 9 Monate und den bedingt zu vollziehenden Teil auf 21 Monate (bei einer Probezeit von 2 Jahren) fest. Es verpflichtete X._, die Interventionskosten der Privatklägerin im obergerichtlichen Verfahren zu bezahlen. C. X._ beantragt mit Beschwerde in Strafsachen, das Urteil des Obergerichts des Kantons Bern sei in Bezug auf den Sanktionspunkt und die Kostenfolgen aufzuheben. Er sei zu einer bedingt vollziehbaren Freiheitsstrafe von 18 Monaten zu verurteilen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Er ersucht zudem um unentgeltliche Rechtspflege und Verbeiständung. D. Das Obergericht und die Generalstaatsanwaltschaft des Kantons Bern verzichten ebenso wie die Privatklägerin A._, die zur Vernehmlassung im Kostenpunkt eingeladen wurde, auf eine Stellungnahme zur Beschwerde.