A paper wallet is simply a public and private key that are written on paper, rather than stored digitally (in a text file or document).
You can create a paper wallet by any of the following methods:
Generating a new key pair using the official Account Viewer and then writing it down in a safe place.
Using the official Paper Wallet page to create a key pair ...
I think that currently the best way to store the keys to Stellar account in the form of a paper wallet is mnemonic code as described in SEP-0005. This Stellar Ecosystem Proposal describes how to derive the Stellar key pair from 12 - 24 words you can write down on a piece of paper or just memorize.
For example these 24 words:
reward result tennis clump ...
You have only two secure options and the first one is not as secure as the second one.
First, create a public/secret pair on the Stellar.org account viewer. This is the only web site that has our approval since it is the very own foundation's site. It may suffer from man-in-the-middle attacks, like malicious programs fishing for crypto accounts, shady ad ...
Send them to https://www.stellar.org/account-viewer and let them create their own accounts. Insist on saving their own public/secret key and not sharing it with any person or webpage.
Then ask them for the public key so you can send them one XLM in order to activate the account so they can check their balance and see everything is working fine.
Then they ...
If you want to make it secure, create a key pair directly in browser, and never send secret key over network (even if it's your own API).
With Stellar JS SDK:
//generate an account
var pair = StellarSdk.Keypair.random();