Interestingly enough, nobles did not eat a lot of fruit as evidenced by their poor teeth/bone health. They thought fruit was for the poorer classes. It is known they did eat dates, an expensive and exotic import from Northern Africa.
According to the website Middle Life and Times - the following fruits were imported into Europe:
- Apricot - from Armenia
- Plums - from Syria
- Peach - from Persia
- Cherry from Cerasus
- Lemon - from Media
- Pomegranate and Quince - from Crete
- Pear and Apple - from Greece
- Oranges - from China
Fruits that have disappeared include sarb and carob.
Romans used a citrus fruit called a citron which no doubt made it to European hands.
Medieval Cookery has a wonderful, detailed listing by date of fruits and their varieties.
Old Cook has some interesting information about the different fruits and origins. For example, the orange. During the early middle ages, only the bitter orange was known (which was too bitter to eat outright) and the sweet orange (that is edible without cooking) wasn't known until the 15th century. Other fruits include blackberry, figs, and apricots. The site even includes a few recipes.