How do pool operators do their hashing?
A pool will generally create a unique merkle root for each getwork request by a miner.  If it accepts difficulty 1 shares, the miner can spend an average of about 4,000 Mega-hashes on that block (and will earn an average of 1 share per getwork).

To create a block header for each miner, the pool operator changes some unique information in the first (generation) transaction of the block, and then rehashes the block to create the merkle root.  If done naively, this will take O(N log N) sha256 hashes (where N is the number of transactions in the block being mined).  By saving some information from computing the last merkle root, you can recalculate a change in the generation transaction with only O(log N) hashes.

With hundreds of transactions per block the ratio of hashes performed by the pool operator and the miners is over 100 million to 1.

For an even greater savings, pools can accept a getblocktemplate api request instead of a getwork request.  This mode allows the miner to generate his own block headers and mine for an average of 10 minutes before needing to be refreshed by the pool.