First, make sure they know that:
- The purpose of exams is to test students' knowledge and understanding.
- The burden of proof is on their side, that is, blank/unreadable sheets work against them.
- The teachers might choose to decipher some of the messy work, but this choice is intrinsically unreliable, erratic and may produce unfair results.
- The teachers grade papers according to their whimsy and the fairness relies on trust in the faculty. The fact that some professor is your teacher is a display of institution's trust in that person. There has to be some amount of goodwill involved, and it is there (i.e. in the teachers).
There are several methods I have seen in practice, some better, some worse, decide what fits your style by yourself.
- Use "clarity points". For two correct proofs, the one which is easier to understand is simply better. Let the students know there are such points. Personally I had used 1pt on [0pt,10pt]scale, students didn't liked it, but it did make the solutions better. It also had some funny side effects, like more students preferring to return an empty sheet (100% clarity) than a bit of something (often 0% clarity), if they were uncertain about it.
- Let the students explain (e.g. assign 0 points and make them come to your office). This is time consuming and tricky, because students might want to update their solution. However, according to my experience, it is frequently the most fair way.
- Time-limit your grading process. If you can't understand it, it is unclear; inference with huge mental leaps is invalid.
- Assign enough time, so they can rewrite their solutions (unclear solution is worth 0 points).
- Request a "clear solution rewrite" with no strokes, linearly ordered, etc. This is related to previous bullet, some students still won't do it, but many will, and it is justifiable to have much higher "unreadable" threshold (for example: Mr. Student, please look at this <huge stack of nice, clean solutions>, are you sure that your work is as easily readable as these?).
- Request solutions in LaTeX (e.g. for homework or take-home exams). Many students rebel against it, but in my experience (from both student and teacher perspectives) it is one of the best solutions available.
- Use answer sheets. Unsuitable for wide range of question types.
- (for computer-science exams) Require code indentation. The rules are clear enough that it's fairly objective to decide if the code is correctly indented or not. Helps a lot. Some require underlining keywords, but that's kind of extravagant.
I hope this helps ⌣¨