When you switch from one program to another on your synthesizer or on another MIDI keyboard, a number corresponding to that program is sent out as a Program Change Message via MIDI.
You can record Program Change Messages with or separate from the notes, that is, afterwards or before.
You can record Program Change Messages on their own tracks, separately from the notes to which they belong. As long as you set the two tracks to the same output and MIDI channel, the MIDI instrument identifies them as two simultaneously created recordings.