I know that the yellow paper does not specify how transactions are to be ordered in a block and this is up to the miner to decide. But I am interested in how this is practically handled (I assume not calling some rand function to get ordering). This answer to a related question suggests that gas price plays a role. How does, e.g. geth order transactions during the mining process?
You've misunderstood the steps. But close!
Consensus is easily misunderstood.
The fundamental problem first solved by Bitcoin was how to reach eventual consensus among nodes that do not know or necessarily trust each other. Add money to the environment and it becomes an adversarial environment. This is in no way like the situation in a typical cluster of computers that do know each other and do trust each other.
We get a hint about how to solve it from transaction logs employed by databases. If one has a replayable log with all the inputs in the right order, then one can reconstruct a database. It's not important to have "the state" if you have the inputs that created that state.
There is a non-obvious challenge to deal with. Given physics, it is not possible for all nodes to learn about all transactions at the same time or even in the same order. It will (probably) never be possible to make everything as fast or faster than everything else.
In a trustful environment, that could be resolved with accurate, trustworthy timestamps that would help everyone enumerate the "correct" transaction order. In an adversarial environment with no authority, that doesn't work because no one's clock is considered more trustworthy than anyone else's.
So, how to order the transactions?
The mining process collapses that ambiguity. The "winning" miner earns the privilege of setting a de facto network transaction order, for one block. Importantly, this is not even an attempt to resolve the temporal order of transactions. In fact, gasPrice, is a way to queue jump. One can probably incentivize a miner to include a transaction sooner by attaching a high bid. Conversely, one can save on transaction fees by being patient.
Nothing happens anywhere until nodes receive news of transactions included in blocks. Transactions in blocks are well-ordered. The blocks themselves are well-ordered. So, the chain of blocks is a well-ordered set of all transactions that have happened.
Each full node, not just the miners, processes transactions completely, reaching their own conclusions about state changes. This is very much like replaying a transaction log because everyone agrees on the inputs and the order of those inputs. The functions are deterministic (strict requirement) so there can be no disagreement between well-functioning nodes at the same block height.
Blocks have time-stamps but transactions don't. Block time is the minimal resolution, and all that can be said is that all transactions in a block were mined at that block time, in the order of inclusion. Each transaction executed in the context left by the previous transaction.
Miners have non-trivial privilege. Working together they can censor transactions. They can play with timestamps and transaction order, if there is selfish benefit doing so. This can be important in contract design when factors such as "deadline" exist.
In any case, the consensus resolves transaction order. Nodes figure out the state for themselves.
Hope it helps.
p.s. There is a lot more going on in mining but I wanted to focus on your question.