They can be found flying above any island, and come in six varieties: White, Green, Red, Yellow, Black and Blue. They are only present during the day, vanishing as soon as the sun sets and reappearing once it rises again. Each variety drops 1-2 feathers of it's respective colour which can be traded in for rare items at the Sea Collector.
Birds killed above water will float, allowing you to loot and hunt them at sea.
If you climb high enough, birds can be shoot down with a sword. :)