In an abstract, Brainerd at al. (2004) report the presence of yawn-like behaviors in "cartilaginous and ray-finned fishes, a lungfish, salamanders, caecilians, mammals, turtles, lizards, an alligator and birds".
So clearly the motor patterns necessary for this behavior evolved before air breathing and apparently have been conserved for ~400 million years. They reject the increased oxygen delivery hypothesis and associate yawning with stretching:
Yawning also has been thought to serve a similar physiological
function to stretching. We measured the stretching movements of fins
and limbs in association with yawns, and found that they follow the
same movement pattern as jaw opening and closing. This lends support
to the existing hypothesis that yawning and stretching serve a similar
function, but the detailed nature of this function remains unclear.