I was on the seat in my plane today when this thought arose. Is it possible that air carriers have cameras fitted inside planes? Similarly is it legal for governments to have cameras fitted inside restrooms of airports? The question is important because there is a possibility of the photos getting tampered and misused in the Internet.
Asking what's “legal” for “governments” could bring up some interesting philosophical questions but generally speaking there are no strongly binding global rules beyond what states commit themselves to through treaties, certainly not regarding privacy. Therefore, what is deemed legal could vary a lot between countries.
I would also question that government surveillance as such is the main issue here, at least when it comes to toilets. Governments or their security apparatuses would probably be more interested in who talks to who and that sort of thing rather than having pictures of people in various states of undress. I would think that the rogue surveillance employee who wants to satisfy some personal vendetta or make money on the side by selling pictures would be a more plausible risk.
Also, in many countries where rules about privacy might exist and matter, airports are typically not directly operated by the government so I guess the usual regulations regarding private CCTV do apply (except of course when law enforcement is investigating specific criminal activity, in which case another set of rules apply). However, I am not sure privacy laws really make a big difference between toilets and other places. CCTV creates risk for privacy even outside of toilets and you could make a case against video surveillance based on that but in most countries rules limiting use and retention of the pictures are deemed to be enough to mitigate it (i.e. the mere possibility for pictures to be misused, which is always there, has historically not been enough to move countries to ban CCTV entirely; it's just forbidden to broadcast the videos).
Where things become interesting and perhaps more travel-related is on the plane itself. I have no idea what laws would apply or if airlines use video-surveillance in the air at all.
Finally, toilets in museums, train stations, etc. are perhaps more likely to be misused in various ways and therefore to be watched so I would be concerned about that before worrying about airports. I have seen cameras in public transport (buses and tramways, with signs informing passengers about it) and at least in one case allegations of cameras in train toilets, promptly denied by the operator. I have also seen toilets with green lighting (making injecting drug use more difficult) in museums.