Well, there are sites for making a paper craft globe of the Earth. Just googling it brings up a ton of different options
, and I won't pick one because I'm not sure whether you want a simple one or a complicated one.
The hard part would be taking one of those templates and replacing the surface with an arbitrary planet. The best way I can think of would be to load a planet into a 3D program, create a UV map that more-or-less corresponds to how one of those paper craft globes is sized up (it looks like there are a few different ways to arrange the facets), then bake the regular texture onto the UV map. Then take it into Photoshop and add the tabs so you can glue one piece to another.