Phones store a rotation flag
Most phones record every frame the same way round, whatever angle you hold them at, and add a small rotation flag to the MP4 or MOV file. The flag says something like "turn 90° when playing". Players that read it show the video upright. Anything that skips it shows the frames as stored, which for a portrait clip means lying on its side.
The flag was set wrongly
The phone chooses the flag from its motion sensors when you press record, then keeps that choice for the whole clip. Film with it flat on a table or aimed at the ceiling and it can't tell which edge is the top. Turn it after recording has started and the clip stays in the orientation you began with.
Orientation lock and in-app cameras
Rotation lock often gets the blame, yet on many phones it only stops the screen turning, while the built-in camera still reads the motion sensors. Cameras inside other apps don't always work that way. Some follow the screen instead, so with rotation lock on, a clip filmed with the phone turned can be saved on its side.
Screen recordings
A screen recording follows the screen, not the motion sensors. If a game or video app draws in landscape while the recorder saves a portrait frame, or a desktop monitor is set to portrait in display settings, the recording can come out turned.
Cameras without a sensor, and converters that drop the flag
Some action cameras, dashcams and webcams have no orientation sensor, or have it switched off, so mounting one upside down gives an upside-down file. Some converters, messaging apps and upload services also re-encode a video and discard its flag without applying it, which turns a clip that used to play correctly.