I have a question about paper wallet. I can print paper wallet using walletgenerator.net. But I am confused about how the things works, where is the data about wallet coins stored? Is there global database of all wallet addresses and transactions? How my public key is paired with my wallet when somebody tries to send me coins?
Is there global database of all wallet addresses and transactions?
Yes, it is called the blockchain. You can browse it through various websites, called block explorers: e.g. http://blockchain.info, http://blockr.io, http://blockexplorer.com. If you use full node software such as Bitcoin Core, you will download a complete copy of this database (currently over 120 GB).
How my public key is paired with my wallet when somebody tries to send me coins?
The paper wallet contains a private key and an address. From the private key one can compute the corresponding public key, and the address is a hash of the public key. You can give your address to anyone, and they can send coins to that address; this means that a transaction is recorded in the blockchain showing a credit of coins to your address. Other than your address, this doesn't need any further information or involvement from you.
You only need the private key when you want to spend those coins. Importing that private key into wallet software, you can make a new transaction to spend the coins that were sent to you. The private key is needed in order to sign the transaction and prove that it is authorized by you, the rightful owner of the coins; but this process does not reveal the private key to anyone else. (As part of this process, the public key will be recomputed from the private key and included in the signature. That is easier than including the public key on the paper wallet.)