They do research, it is quite obvious someone will have in their mind of certain songs, won't they? Some songs as old as the First World War are still known today.
Songs are generally not lost to the world as people may think, but they are just phased out and are not listened to anymore...this does not mean they don't exist anymore. There is a number of multi-billion people in the world...and a lot of old people still know of songs from back then.
Movie staff will just look up certain songs because they in fact can and they have access to a wide variety of music, old and new, of all genres etc. It isn't really rocket science to how they find seemingly lost songs..they ask people they know.
They use Primary sources:
They use search engines, other movies, music history, record disks (they still exist), old day devices, tapes and very old people.
They also use secondary Sources:
They use things like websites, articles online (not from the original author) and plenty of other things you could possibly think of.
They could also advertise online for certain music and maybe a reward for the given song or genre of music.
It is really quite easy to obtain old and almost long forgotten music, they just think of a way and get it even if it is supplied to them by someone.