The Yew is one of the five power trees of the Irish Fire Druids.
It's Ogham representation is Idho (ee-yo). This stands for reincarnation, wisdom, courage and defiance of death. This probably comes from the fact that the yew is one of the only evergreen trees natural to the British Isles. Obviously a tree that lived on throughout the year while others 'slept' for the winter would have been seen as possessing many powers.
Burying thing beneath them would also give them a magical gardian that was there all year.
Their presence in graveyards probably also stems back to the fact of their seeming 'evergreen' powers.