This well-known photograph shows what is possible.
There is a good discussion about this in the National Geographic as follows:
Weasel Rides Woodpecker in Viral Photo—But Is It Real?
The conclusion seems to be that it is indeed a likely result of a weasel attacking the woodpecker which then flies off.
Surely fairies can train certain birds to carry them. After all human fishermen have trained cormorants to help them fish.
If you want to know what it wouldmight look like when a fairy rides a bird, here is a Photoshopped picture from the internet. I don't know the artist.