Here's an image of a cube with lots of edges added. It was created using knife tool and lots of clicking:
What would be the best way to randomly generate such cuts with less effort...?
Rereading the question and answers, there is actually a third way to do this that's very very quick if you just want the surface tessellation. (i.e. you dont want the cuts to be separate objects or meshes)
Make a cube, apply subdivision surface on it (simple, 2 levels), then use the Decimate modifier to reduce the polygon count and apply the modifiers from bottom to top.
Continuing off of AdamTM's answer. Cell fracture creates a lot of separate objects. To get to just cuts on the surface takes a few more steps.