you should protect the paper wallet in protecting plastic first , in other words laminate it. then you can store it anyplace you like and be sure that it is well protected against anything that can harm paper like humidity.
the best place I can think of is a safe if you have one or the same place in your house where you keep your valuables. you may even consider a safety deposit box at a bank.