The solo-miner (or mining pool) typically runs software that makes the decisions. They can often configure that software in any way that they like.
In the case of Bitcoin, they are required to include AT LEAST one transaction (the transaction that pays the block reward). Beyond that they can include as many or few valid transactions as they like as long as they don't exceed any size limits on the block.
When you say "(the transaction that pays the block reward)", does the miner create this transaction himself?
So, based on your answers, it sounds like miners around the globe are independently adding transactions to blocks first, THEN, they start working on the proof of work, correct? This is probably the only sane case because doesn't the POW depend on the transactions in the block itself?