'In' indicates inside of, within, enveloped. The fish are in the ocean. The toy is in the box.
'On' is like attached to, adjacent, touching. The writing is on the wall, The fish is on the stove.
If the birds are 'on' the sky it means there's a surface for them to be connected to, but that isn't the case and also the 'sky' here is more of a place, like the birds