Do transactions happen in an already mined block or a block yet to be mined? As I understand it a miner gets a reward of 25 BTC per block he finds (as of now). I also read that some transaction fees go to the miner who found the block.

How are these two things related?

Also, how can a miner not claim all the fees? Ain't that automatic? Is there something the miner needs to do after he found the block to claim the fee?

How was the system "boostrapped" with the first block ever?
A new block is constructed using transactions from the queue of pending transactions.  The miner repeatedly hashes the data until the result meets the network difficulty level.  The local bitcoin node then broadcasts the block to the network.  The process then repeats with the next set of pending transactions.

The miner gets the block fee as well as all transaction fees for the transactions included in the block.  Note that the miner receives nothing if the block is orphaned because another miner broadcast his block first.  In the case of a pool, the fees are divided among all of the miners in the pool.

Each block contains a coinbase address and this is the address that receives the fees.  The miner can set this address to anything he wants.

Satoshi started the process by releasing the genesis block, which is the initial block in the block chain.