When To Pray: Traveler's Questions: Crossing from Day-Night or Night-Day

Always say the prayer service based on the day and time where you are at the moment you are ready to pray.
 
Flying West
Situation
You fly west and take off before sunrise.
What To Do
If the sun will rise while you are flying, you may say shacharit from the time of alot ha'shachar on the ground below where you are when you begin to pray.
 
Situation
You fly west, taking off during the daytime.
What To Do
Say mincha whenever the sun has gone at least 30 minutes past the local midday where you are at that time.
 
Situation
You fly west into the night.
What To Do
Say ma'ariv. once it is night on the ground below you.
Note On a long west-bound flight, you might not have to say any prayer services, since you might still be covered by whatever prayer service you said before you took off.
 
Flying East
Situation
You cross the international dateline passing through the night and are now back in the day you already experienced.
What To Do
You ignore the fact that you said the prayer service on that day and say it again.
 
Situation
You fly from Australia on Tuesday, departing during the daytime. You will fly into the night of Monday and continue on back into Tuesday.
What To Do
You disregard the fact that you already said ma'ariv for Monday and you say ma'ariv again. If your flight continues until sunrise, you will also say shacharit for Tuesday again.
 
Situation
You fly from Australia on Tuesday morning and cross the IDL during the daytime of Tuesday and are now back into Monday.
What To Do
You do not say any prayer service until your flight crosses into night, whether that happens in flight or after you have landed. You will need to say mincha at some time during the day.
 
Situation
You fly east but you do not cross the international dateline.
What To Do
If you cross into the night, you will say ma'ariv as you normally would do. If you took off at night and cross into daytime, you will say shacharit.
Note When flying east from night into day, there is a very brief time period when you may say shema of the morning, since you may not say shema until alot ha'shachar and must say shema by the end of the third hour of the local day. When flying east, instead of having about 4 hours during which to say shema, you might only have two or so hours.
Note Regarding saying the shir shel yom (psalm for the day of the week), follow the local day.