Unless you use a custom 'Submit for Approval' button, you can't validate prior to submitting for approval. What you can do is add that the checkbox must be true in the Entry criteria for the approval process. If the checkbox is not checked they will receive an error. I fully admit this error is not ideal as it is extremely generic and really doesn;t tell th user what they need to do to correct. It will though, prevent the user from submitting it for approval.
If you still want something more customized you will need to either use Visualforce for a custom page to submit for approval, or you can try to write your own custom JS button to submit for approval that alerts the user they must check the checkbox before submitting for approval,