C-3PO learnt the Ewok language through observation.
A few points from Legends have to be made to come to this conclusion:
- The 3PO-series protocol droids are equipped with a TranLang III communications module. It comes with up to six million galactic languages - common and obscure, organic and inorganic - at purchase. It also possessed phonetic pattern analysers that provides the capability to learn and translate new languages not in its existing database.
- The Forest Moon of Endor was known to exist by the galactic community as early as 3645 BBY. Due to its proximity to the Unknown Regions and local cosmic anomalies, it bore witness to an abnormal number of starship crashes over the centuries. Many animal species were introduced to the planet by such means. As a result of its extremely rich, unique and diverse biosphere, the moon was declared a nature reserve by the Galactic Republic, hence the nickname Sanctuary Moon.
- Besides the dominant Ewoks, Endor was also home to four other similarly primitive sentient species. One of these is the plains-dwelling Yuzzum. The Yuzzum language is closely associated with the Ewok language, and sounds musical in nature. For this reason, Yuzzums are frequently exported as pets despite their sentient status. A Yuzzum was present at Jabba's court, and Yuzzums are also present in colonies across the galaxy despite their primitive hunter-gatherer technology.
- Many Ewoks know the Yuzzum language. C-3PO first communicated with the Ewoks using the Yuzzum language, and gradually pieced together enough to learn the Ewok language sufficiently to be conversational.
As such, the likely sequence of events is:
- C-3PO knows the Yuzzum language and has some knowledge of their origins.
- Despite having a communication problem, he decided to give the Yuzzum language a try since this is their home planet after all.
- As luck would have it, many Ewoks understand the Yuzzum language, so things worked out.
- As the Ewok and Yuzzum languages are very closely related, it's not difficult for C-3PO to eventually learn the Ewok language proper and add it to his database.
This is scraped together from various Wookiepedia articles. You can read up there to see where it's sourced from.
'TranLang III communications module', wikia.com
'Yuzzum (language)', wikia.com