I am wondering another thing:
The fee goes to the miner who first adds it to a new block.
Correct.
So is that baisically the miner who finds a new block?
It is a miner (or mining pool) that solves a new block.
The miner (or pool) keeps track of all the unconfirmed transactions that they've heard about. They choose which of those transactions (if any) they want to confirm and assemble them into a block. They then build a header record for that block that has information about the block of transactions and information about the most recent block that has been added to the blockchain.
They then begin trying to "solve" the block. To do this they calculate a double SHA256 hash of the block header and see if the resulting value is less than the current target difficulty. If it is not, then they modify the block header a little bit and try again. They repeat this process until they either hear about a valid new block from a connected peer or find a solution themselves. Regardless of whether the new block is one they receive from a peer or that they created themselves, they then add the block to their blockchain, remove all the transactions that are in the block from their list of unconfirmed transactions, and start over again.
If they chose to include your transaction in their block, then they get the fee from the transaction and the transaction has it's first confirmation.
And is that then what I read as first confirmation?
Yes. When a transaction first shows up in a block in the blockchain, it is said to have it's first confirmation. Each additional block added to the blockchain on top of that block is considered to be an additional confirmation.
How does a miner know that a transaction was made?
As has been explained, the miner (or pool) is running a full node that is connected to peers (other full nodes in the bitcoin network). When you send a transaction you (or the service that you are using) is connected to other full nodes in the bitcoin network. Each node that receives the transaction verifies that the transaction is valid and then re-broadcasts it to all the peers that the node is connected to. Then each of those peers verifies that the transaction is valid and re-broadcasts it to all the peers that the node connected to. This process repeats until the entire interconnected network (including any miners or pools) have heard about the transaction.
Each node (including miners and pools) keeps its own list of unconfirmed transactions that it has heard about. Eventually if the transaction gets old and hasn't yet gotten confirmed into a block, the node will remove the transaction from its own memory to make space for newer transactions. If it hears about the transaction again, it will add it back into its list.
I mean where are they stored before they are recorded as a part of the blockchain?
Every node on the network stores its own copy of the transaction for as long as the node is programmed to. There is no minimum or maximum amount of time enforced by the protocol. Some nodes might be written to remember the transaction forever, others might be written to forget the transaction immediately. Typically it seems that most of the network has forgotten about the transaction if it isn't confirmed yet withing 3 days or so.