The earliest copy of this melody is from 1893, with the song "Good morning to all" by Patty Hill and Mildred J. Hill. It was published in a songbook titled Song Stories for the Kindergarten.
The lyrics to "Happy Birthday to you" appears in the early 20th century. The first reliable source for these lyrics being used with the "Good morning" melody is from 1911, although most likely that melody was used from the start.
The Copyright Act of 1909 allowed for 28 years of copyright plus another 28 if renewed. It was not renewed, which means the copyright for the melody ended in 1921, and if it had been renewed it would have ended in 1949.
The lyrics were printed in full in 1911 and so fell out of copyright in 1939, as it was not renewed, and if it had been renewed it would have fallen out of copyright in 1967. Most likely the lyrics are older, though.
As such, the song and its lyrics are in the public domain.
So why do you have to pay money to Warner/Chappell to use it?
This is because in 1935 The Summy Company registered the song for copyright, crediting authors Preston Ware Orem and Mrs. R.R. Forman. This copyright was bought by Warner/Chappell in 1988. That copyright would have expired in 1991, if not for the 1976 copyright act that extended copyright 75 years, and then the 1998 copyright act that extended it to 95 years, so that copyright for Happy Birthday to you is now set to expire in 2030.
Now it is clear, and has been clear for several years, that this copyright claim is false. So why has it continued? It has continued because it costs millions of dollars to fight a legal battle over a copyright claim, no matter if you win or lose. Paying the license fees is cheaper, even if you are right. Copyright in this sense works like a form of state-sponsored mob activity: pay up a little bit or we use the legal system to destroy your company through lawyers' fees.
But Preston Ware Orem was a serious composer, who never seemed to have claimed to write this song, so the 1935 copyright claim is very hard to understand, and I for a long time thought that The Summy Company perhaps filed this song for copyright without Mr Orems knowledge. But in June 2013 a class action lawsuit was brought against Warner/Chappell. This lawsuit aims to get all license fees Warner/Chappell has received for the song paid back. Most of that will go to paying the lawyers, but still. Warner/Chappell, if they lose, will have to pay back their earnings to the song, and pay their lawyers, which will hurt.
In this class action suit something interesting is mentioned: the 1935 copyright registration is not for the song or for the lyrics, but for a piano arrangement of the song. Warner/Chappell's claims to have the copyright for the song is simply false. When they bought The Summy Company in 1988 it was estimated that the company was worth $25 million, and that $5 million of that was the copyright to Happy Birthday To You. Reasonably their lawyers must have looked at the copyright registration and realized that it was for a piano arrangement and not for the song, which means that Warner/Chappell has by now been committing copyright fraud for 25 years, which is indeed the claim of the lawsuit.
As for early recordings, the song is so old that the recording industry didn't exist. Its popularity therefore spread in other ways early on. Its increased popularity and spread outside America is most likely through movies and I would venture that the spread outside America is mostly post-war, but I can't find a source for that.