Pretty much what it says on the tin— usually if something is "X of Y", it is, usually because "X" is related to, or is of "Y" (e.g. "people of faith" means people who have faith) In this case however, "bird of prey" doesn't mean that the bird is prey, but rather, that it eats prey, which is the opposite (it's the equivalent of construing "people of faith" to mean "atheist"). What is the reason we call birds that eat prey "of prey", instead of "predator birds"?
From a grammatical point of view, "prey" preceeded by "of" is a genitive.
In many languages such as Latin, English or French, the genitive generally indicates the possession. But in this case, the genitive denotes a description, as for "a man of honour" or "the day of reckoning".
Bird of prey is a translation of the medieval latin "avis praedae". It may be a direct translation from latin or derived from its french equivalent "oiseau de proie".