This link leads to many threads about how to do a paper wallet. It may be different depending on the wallet you use.
https://bitcointalk.org/index.php?action=search2The most important thing is to think in terms of theory. In bitcoin there are public keys for receiving payment and private keys for spending. If you do not have complete, exclusive control of your private keys then you simply do not have bitcoin, IMO.
Online wallets typically are running a wallet for you. Of course if they are hacked, or dishonest, or get wiped out in a tornado then your money is gone with no hope of recovery. In bitcoin you must do all the work. You are the CEO, the security team, etc. There is nobody superior to your authority. So be careful.
What I do is store most bitcoin offline in cold storage in a bank vault (banks are still good for some things). I also keep a small amount on my phone using an online wallet system. Even though that money is more vulnerable, it is so convenient that it is worth the risk to me.
You may want to develop your own policy, but if at all possible... trust no one.