Disclaimer: The great article of Reginald Smith's "A History of Coffee" is a must read for everybody who has interest.
One of the stories of coffee's discovery, which is more common than others is as follows: Kaldi, a monk and a goatherd, sees his goats gets excited after eating some berries. Then, prepares the coffee from the beans of the berries.
The second, less common one is as follows: Yemeni priest Ali bin Ömer banished to the mountains of Yemen. There he discovers the beautiful flowers of the coffee tree, then the beverage.
Etimologically coffee roots from Arabic ḳahwa (قهوة). The root of Arabic word is unknown, but some say that it is originated from some poetic form of a word for wine as it is forbidden in the Arabic world. This name is more or less similar all around the world today: Turkish kahve, French cafe, Italian caffe, German kaffee, Dutch koffie, English coffee, Latin coffea.
The wild Coffea arabica is known to be cultivated in Harar valley of Ethiopia at earliest AD 850.
The beverage stayed local for a while, then became known among Arabs. East Europe became aware of it through Ottomans; Especially Austria and Italy. Then, the rest of the world.
Coffee was a very valuable asset even in those years. Therefore, strangers were not allowed to access green beans for long in the Arabian peninsula. Baba Budan, an Indian Pilgrim, was the first one who can manage to take out seven coffee seeds out of Mecca to Mysore strapped to his belly. Then, cultivation out of Arabian Peninsula and East Africa boomed.