New Cool Thang asks what evidence we have of a Heavenly Mother:
Next year’s manual for Relief Society/Priesthood will be Gospel Principles, and chapter 2 begins with the following quote:
“All men and women are . . . literally the sons and daughters of Deity. . . . Man, as a spirit, was begotten and born of heavenly parents, and reared to maturity in the eternal mansions of the Father, prior to coming upon the earth in a temporal [physical] body” 
The concept of Heavenly Parents alludes to the teaching within the church that there is a Mother in Heaven. I went over a brief survey of statements regarding Heavenly Mother, mostly from the church website and magazines, and wanted to put up some characteristics that have been taught about her by prominent church members.
First, she was involved with Heavenly Father in the pre-mortal world with the teaching of spirits.  Had we not known in our pre-mortal existence that we could become like our Mother in Heaven, we never would have come.  Her glory was like the Father’s Glory, and she was “side by side with Him”  Further She is “equally exalted” with Heavenly Father.  She was Essential to Him.  She has endowed her special traits and attributes upon her daughters, such as love, charity, and faithfulness. Coarseness and vulgarity is contrary to Her nature.  She is the “ultimate in maternal modesty, of the restrained queenly elegance” and Her Influence upon us will be great if we live our lives here “so as to return there”  She values her children “beyond any measure”  In the grand order of things, we do not pray to her, but this lack of prayers in no way denigrates or belittles her  This may be perhaps because she is in perfect unity with her spouse, and thus prayers to him are equal to prayers to her.  Alternatively, she is prayed to (sort of) each time the Song “Oh My Father” is Sung.
There is some disagreement as to the origin of teachings regarding Heavenly Mother within the church, with possible alternatives being that Joseph received a revelation and shared it with Zina Huntington, that Joseph Revealed it to Eliza R. Snow, and that Eliza, having claim to prophecy in her own right received it directly from God. Perhaps all three occurred.  Alternatively, other members has referred to teaching of her as a case of “over-belief” (sorry, no citation available)
In recent years, the church has publicly clarified some points in regards to our Mother in Heaven, noting that she is not referred to as “The Mother” among church members and acknowledging that there are no teachings about her in Latter-day Saint Scripture.  This should not concern members however, as she is mentioned in conjunction with the Father as Heavenly Parents in the First Presidency Declaration regarding Families , and Joseph Fielding Smith noted “the fact that there is no reference to a Mother in Heaven in either the Bible, Book of Mormon or Doctrine and Covenants, is not sufficient proof that no such thing as a Mother did exist there.”  In any case, while the Mother may seem veiled to us, the typical saint trusts that God has his reasons for revealing as little as he has.  And in any case, the Lord has provided for us an ample Role Model and Confidant for both Sexes in the Savior Jesus Christ. 
1. (Joseph F. Smith, “The Origin of Man,” Improvement Era, Nov. 1909, pp. 78, 80).
2. Julie Beck (“You Have a Noble Birthright,” Liahona and Ensign, May 2006, 106, 108) also in Aug 2008 Ensign, p 69
3. Joseph F. Smith, Teachings of Presidents of the Church: Joseph F. Smith, 148; also Gospel Doctrine, 13
4. Melvin J. Ballard (Apostle), Journal History, 8 May 1921, p. 2
5. Ida Smith, “The Lord as a Role Model for Men and Women,” Ensign, Aug 1980, 66
6. James Talmage, Deseret Evening News, April 28, 1902
7. Vaughn J. Featherstone, “A Champion of Youth,” Ensign, Nov 1987, 2
8. Spencer W. Kimball, “The True Way of Life and Salvation,” Ensign, May 1978, 4
9. Spencer W. Kimball, “Privileges and Responsibilities of Sisters,” Ensign, Nov 1978, 101
10. Gordon B. Hinckley, “Daughters of God,” Ensign, Nov 1991, 97
11. Theodore M. Burton, Love and Marriage, BYU Speeches 3 June 1986; See also Erastus Snow (Apostle), Journal of Discourses, vol. 19 (3 March 1878)
12. See Wilford Woodruff, Latter-day Saints’ Millennial Star, 9 April 1894, p. 229 for Eliza receiving the revelation, Joseph F. Smith (President), Deseret Evening News, 9 February 189 for Joseph revealing it to her, and Linda P. Wilcox’s article in Sisters in Spirit: Mormon Women in Historical and Cultural Perspective for Zina receiving the revelation.
13. Lds Newsroom, Response from The Church of Jesus Christ of Latter-day Saints to Newsweek cover story, 10 September 2001 edition.
14. The Family: A Proclamation to the World
15. Joseph Fielding Smith, Answers to Gospel Questions 3:142
16. Patricia T. Holland, “ ‘One Thing Needful’: Becoming Women of Greater Faith in Christ,” Ensign, Oct. 1987, 26
17. Ardis Parshall, Does Jesus Understand Postpartum Depression?
Some interesting additional teachings of William Phelps were added by some of the many commentators :
On December 25, 1844, Phelps also wrote a letter to William Smith:
A heap of dust alone remains of thee, ‘Tis all thou art and all the proud shall be,” while Mormonism, from an Abel, though dead, yet speaketh; from an Elijah though translated in a fiery chariot to heaven, yet, returns in glory with Moses, and blesses Jesus at the transfiguration on the mount! O Mormonism! Thy father is God, thy mother is the Queen of heaven, and so thy whole history, from eternity to eternity, is the laws, ordinances and truth of the “Gods”-embracing the simple plan of salvation, sanctification, death, resurrection, glorification and exaltation of man, from infancy to age, from age to eternity, from simplicity to sublimity: from faith, repentance, baptism, reception of the Holy Ghost by the laying on of the hands, to washing, anointing, presence of angels, the general assembly and church of the first born; to the unspeakable glory of seeing God and the Lamb, and to spirits of just men, made perfect, and to be ordained unto eternal life! (W. W. Phelps, “The Answer,” letter to William Smith, December 25, 1844, Nauvoo, Il, Times and Seasons 5 (January 1): 758.
Here’s the relevant excerpt from Phelps to William (pub. date is Jan 15, 1845 – they were running about 6 weeks behind I think, so this may have appeared in March 1845). Phelps clearly connects the terminology with OT passages and temple terms – an extrapolation?:
O Mormonism! Thy father is God, thy mother is the Queen of heaven, and so thy whole history, from eternity to eternity, is the laws, ordinances and truth of the “Gods”-embracing the simple plan of salvation, sanctification, death, resurrection, glorification and exaltation of man, from infancy to age, from age to eternity, from simplicity to sublimity: from faith, repentance, baptism, reception of the Holy Ghost by the laying on of the hands, to washing, anointing, holy conversation, baptism for the dead, to the presence of angels, the general assembly and church of the first born; to the unspeakable glory of seeing God and the Lamb, and to spirits of just men, made perfect, and to be ordained unto eternal life!
And again, we exclaim, O Mormonism! No wonder that Lucifer, son of the morning, the next heir to Jesus Christ, our eldest brother, should fight so hard against his brethren; he lost the glory, the honor, power, and dominion of a God: and the knowledge, spirit, authority and keys of the priesthood of the son of God.
Christ kept his first estate-Lucifer lost his by offering to save men in their sins on the honor of a God, or on his father’s honor.-Christ hated sin, and loved righteousness, therefore he was anointed with holy oil in heaven, and crowned in the midst of brothers and sisters, while his mother stood with approving virtue, and smiled upon a Son that kept the faith as the heir of all things! In fact the Jews thought so much of his coronation among Gods and Goddesses; Kings and Queens of heaven, that they broke over all restraints and actually began to worship the “Queen of heaven,” according to Jeremiah.
A Hymn was written as if declared by Joseph Smith, now dead and in heaven:
Come to me, here are Adam and Eve at the head Of a multitude quicken’d and rais’d from the dead: Here’s the knowledge that was, or that is, or will be— In the gen’ral assembly of worlds: Come to me.
Come to me; here’s the myst’ry that man hath not seen; Here’s our Father in heaven, and Mother, the Queen, Here are worlds that have been, and the worlds yet to be, Here’s eternity,—endless; amen: Come to me.