"Birds fly in the sky."
"The only time you can use the 「を」 particle for intransitive verbs is when a location is the direct object of a motion verb as briefly described in the previous section" http://www.guidetojapanese.org/learn/grammar/in-transitive
を does have other functions beside indicating the direct object of an action. it could indicate an area traversed, which is the case here, or the period of time over which the action takes place, it could as well indicate the object of desire or hate, just to name a few.
There may be some confusion because of English language conventions, but this is a generalized statement that birds fly (in) the sky like pirates sail (on) the seas. If you remove "in", the meaning should be clearer. Sky is the object of the action and that form uses を.