Should I just write it on a piece of paper? What do you guys use?
Yes, paper wallets are among the safest wallets you can use. There are risks as well though...
Other safe options include hardware wallets and cold storage.
Anyway you can use any wallet you want, but there are 3 main things to keep in mind in order to have your funds really safe:
1. The safest wallets are never online. Thus you cannot spend their money, but you can only store it for the long term.
2. To be really safe, backup your private keys and store them in - at least - 3 different places (for example a piece of paper, a USB stick and maybe your brain).
3. It's not important only which wallet you use, but also who can access such wallets. Stolen funds can come even from relatives, friends or collagues. Take care of your wallet, private keys, seed and store their informations only to very trusted people (for example your wife/husband).