Through the process of mining, a miner produces blocks, which contain transactions - so, miners do not 'mine' individual transactions.
In a Proof-of-Work system, miners compete to solve a cryptographically difficult problem in order to mine new blocks.
Once a block is added to the blockchain, all of the contained transactions are executed (these could include simple value transfers or smart contract functions that modify state) and the miner receives the block reward (say, 3ETH) and all of the transaction fees (gas) in the block.
As well as transactions, a block also contains the hash of the previous block (its 'parent'). This way, blocks can be verified in the context of the entire blockchain. This article explains how the Ethereum blockchain uses Merkle trees/proofs to achieve this.
As for the proof that a miner processed a block, each block contains this publicly-available data in the 'block header'. Have a look at block #4638064 on both Etherscan and Etherchain (two examples of block explorers) and you'll see that an account with the address 0xea674fdde714fd979de3edf0f56aa9716b898ec8 (and 'username' ethermine) mined this block.
So - your assumptions were definitely along the correct lines! As with any new, seemingly complex technology it is very easy to get lost in the terminology (which is often loosely defined anyway). 🤠