I actually use google sketchup for getting the shapes right, it's fast and easy, and theres some extremely convenient unwrapping/tab adding plugins specifically for papercraft design, + it works on mac.
the art/textures are then done in photoshop, some trial and error is necessary for some things, but all in all it's not so hard.