While the block header is always the same size, one component of the block header is the Merkle Root which changes with each included transaction. The Merkle Root is a hash based on a Merkle Tree of all the transactions of the block. Creating the Merkle Tree requires 2(n-1)+1 hashes. The Merkle tree will need to be updated periodically to include new transactions as they occur.
To save computing power in pool mining the pool server computes the Merkle Root and then provides it to all miners in the pool. In solo mining each miner will need to compute and update the Merkle Root. Current transaction volume is relatively low so the amount of computing power required to update the Merkle tree isn't significant. However if Bitcoin ever reached VISA level transaction volume (~4000 transactions per second) computing the Merkle tree would require significant computing power, possibly even dedicated CPU/GPU acceleration just for Merkle tree calculation.
Information on scalability issues for high transaction volume:
Capabilities of Bitcoins and their place in the future