> Starting on pen and paper

This is really the secret. Pencil, pen, whiteboard, crayon, whatever. Anything that lets you rattle off half a dozen super low detail sketches in under a minute will work. It doesn't need to be pretty either. Just as long as it's enough to give you a feel for interacting with the page as a whole.

Once you have a good solid idea for how you ultimately want it to come together then you can move to a computer to drill down into the individual details, but for getting from zero to concept there's no substitute for analog tools.