I think David ilustrated very well how things works, but I feel your question was not fully answered since you asked about time. So I will try to complete the answer above.
As David said in the previous answer, when you send a payment (or transaction), somethings happen at first: the sending of the transactions to one or few nodes, the broadcast of that transaction to all nodes (including miners), the placing of that transaction on a block to be mined.
All this envolves many parties but it takes less then a second or, at most, a few seconds. At this moment, all the nodes (including mining nodes) must have your transaction in a pending state. In fact, the transaction is on what is called a mining pool. It is there, but it was not included in any block yet. As David said, only by including a transaction on a block, receiver of that transaction can be safe that you will not spend the money in other place.
SO, AT THIS MOMENT, EVERYBODY KNOWS ABOUT YOUR TRANSACTION, BUT IT IS NOT CONFIRME YET.
Then, mining takes place. Mining a block takes on average 10 minutes. If you paid a good fee for that transaction or if the mining pool does not have many transactions, your transaction should be included in the next block to be mined. And this will be done by all (or, at least, most) of the miners.
As David said, mining consists of solving a puzzle. You take a set of transactions (which forms a block) and try to find a number that comply with a predetermined rule (the puzzle). The original block plus this found number is what is called a mined block. When one miner solves this puzzle, it will broadcast the block with the solution and all other nodes (including other miners) will verify it and put the block in the chain. *
NOW, RETURNING TO ANSWER ABOUT TIME.
We have two scenarios to explain how your transactions were received so fast. First, it is possible that the party that received value from you, asked the network (which means, asked one of the nodes of the network) if your transaction was received and is on the mining pool. For very small payments, it can be enough to trust you will not try to spend this money again. And this can be very fast, can take less then a second or at most few seconds.
The second scenario is when the receiving party only consider the payment done when it is confirmed, which means, a block with your transaction is included in the chain. How long does it take then? There is the time your block sits on the mining pool waiting to be include in a block. And there is the minig time. When is said that the block is mined on average in 10 minutes, it means, statistically, that it can take an hour or few seconds.
So, if you were very lucky, the block including your transaction started beeing mined soon after your transaction arrived at the mining pool. And was mined very fast. This could explain a fast confirmation. It can happen but it will be an exception.
(*) There are complications when two miners find the solution at the same time. Because of that, one transaction can really be categorized as confirmed only when six more blocks are put on the chain after the one that contains the transaction. But for transactions with value bellow $1000, it is safe enough to assume confirmation with just one block. For more on that see https://en.bitcoin.it/wiki/Confirmation