{..} It is said that if you create a paper wallet nobody gets to your coins.
It depends on the way you create a paper wallet. For example, if you generate a private key in an insecure device and print it, then there is a high chance you will loose Bitcoins send to that address.
What about the private key? Is it store somewhere in the servers?
No. I think you don't know what a paper wallet is. Generally, a paper wallet is storing Bitcoins on a physical paper/document*.
Private keys are printed onto a paper. If you generate private key using an online wallet, Blockchain.info for example, then your private key is also in their server and in your paper -- doing this is highly discouraged. Don't generate private keys online!
* From wiki.
How does blockchain.info or coinbase recognise my private key and matches it with my address? I think there is a simple answer to it but i cant think of it
Addresses are calculated from private key and not vice versa. I recommend you to print both address and private key onto a paper when you create a paper wallet. So you can avoid confusions.
Edit:
I need to learn to explain myself
I wanna know how the private key works in the whole system not how to do it
https://en.bitcoin.it/wiki/Private_key