You will need to setup the server validations in two parts. There is the validation itself, for this you apply the Server Behaviors > WA Validation Toolkit > Server Validations. Make sure to set the failed redirect to the checkout page to stop it from proceeding.
Once you have configured the server validations you will need to craft your error messages. For this just put in some text next to a form element then highlight the text and go to WA Validation Toolkit > Validation Show If. Then select the corresponding server validation that you would like to trigger the error message in the 'if validations fail' area.
If you have not used the server validations before I would suggest that you add it to a single form element first, then apply the validation show if for the error message and test it out. This should get you going.