When did Christmas (the birth of Christ) first begin as a Christian celebration? I remember hearing something about a true Saint Nicholas who maybe helped poor children or something, but to be honest, I really don't know much about when Christmas began to be celebrated by Christians.  I do know that the Orthodox Church celebrates it on a different day.

Did it begin in the Catholic Church?  If so, when did it become adopted by the Orthodox Church?
St. Nicholas of Myra predates the Great Schism by over 600 years. His feast day traditionally was December 6th, but has been taken off the Catholic calendar recently. Orthodox celebrate the feast of the nativity on the same day Catholics do, but their celebration with gifts, etc... is 12 days after (like it is in Spain and parts of Louisiana) on 3 kings day (feast of epiphany (catholic) or Theophany (orthodox)). That's January 6th, which remembers when the 3 kings came, quite a bit later than Jesus' birth (unlike in popular depiction). 

St. Nicholas's feast day, like St. Stephen's who the song "Good King Wenceslas" takes place on, is conflated with Christmas for a few good reasons. Namely charity. On St. Nicholas's feast day there is a tradition of children leaving their shoes out for him to come and fill.  

The older feast is the feast of the annunciation which apparently goes back to when the Anno Domini system was established. It was and is March 25th, and that was the greater of the two feasts in those days. Like the annunciation of Mary and John the Baptist, Jesus' annunciation feast day is 9 months previous to His birth. So, even in 731 there is a tradition of having Christ's birth be celebrated on December 25th.

However, there's nothing particularly special about the times and seasons of liturgical feasts. They arise through tradition and not through scripture. But the indisputable fact is, it is old.