1. Check everywhere. By this, they mean open all the obvious and not-so-obvious doors in a level so you can visit the entirety of a stage.
2. Clear the stages: The most basic way of upping your clear % is to clear a stage. It'd be better if you uncovered everything in a level to raise the clear % higher, but just getting past a stage is good enough to bump up the number.
3. Grab Orange Cube Items: These orange cubes contain rare items that increase one's clear percentage. Finding the boxes and getting the treasures is another way of increasing your clear %.
4. Get Character Trophies: While the Dojo wasn't clear about them, you can be sure that grabbing a character trophy will net you some points towards that clear percentage.

Via Smash Bros. Dojo