Finding Historic Recordings Free Online
There are currently thousands of recordings, dating from the 1890s through the 1940s, which are available for free online.
Here are good vintage recording sites I know about. These are all "legit" sites, and do not include any sites where questionable filesharing might be taking place.
The Library of Canada has an amazing site called the Virtual Gramophone. This is supposed to be primarily Canadian content, but many of them seem to be US and French recordings which were released in Canada. The recordings range in date from the beginning of the 20th Century up until the 1940s. The French stuff seems to run later. Perhaps French copyright laws aren't as insane as those in the US.
http://www.collectionscanada.ca/gramophone/index-e.html
The best source for wax cylinder recordings is the UC Santa Barbara Cylinder Preservation Project, with thousands of recordings available for free download.
http://cylinders.library.ucsb.edu/
For some more really early stuff, there is "tinfoil.com". This is primarily devoted to late 19th and early 20th Century wax cylinder recordings. Most are in "Real Audio" format, so they aren't intended to be copied (that doesn't mean they can't be--but I am not advocating such behavior on this website).
http://tinfoil.com/
Also in Real Audio format, but focusing on the '20s and '30s is "Radio Dismuke". It is also available as web radio or on iTunes.
http://www.dismuke.org/radio/
A similar service is offered by the "Red Hot Jazz Archive", which has information on thousands of bands as well as many, many recordings. http://www.redhotjazz.com/
The Library of Congress has an interesting assortment of offerings. Click on "Performing Arts: Music" for online music, sheet music and other content: http://memory.loc.gov/ammem/index.html
First World War.com http://www.firstworldwar.com/audio/