Several permutation strategies are often possible for tests of individual terms in analysis-of-variance (ANOVA) designs. These include restricted permutations, permutation of whole groups of units, permutation of some form of residuals or some combination of these. It is unclear, especially for complex designs involving random factors, mixed models or nested hierarchies, just which permutation strategy should be used for any particular test. The purpose of this paper is two-fold: (i) we provide a guideline for constructing an exact permutation strategy, where possible, for any individual term in any ANOVA design; and (ii) we provide results of Monte Carlo simulations to compare the level accuracy and power of different permutation strategies in two-way ANOVA, including random and mixed models, nested hierarchies and tests of interaction terms. Simulation results showed that permutation of residuals under a reduced model generally had greater power than the exact test or alternative approximate permutation methods (such as permutation of raw data). In several cases, restricted permutations, in particular, suffered more than other procedures, in terms of loss of power, challenging the conventional wisdom of using this approach. Our simulations also demonstrated that the choice of correct exchangeable units under the null hypothesis, in accordance with the guideline we provide, is essential for any permutation test, whether it be an exact test or an approximate test. For reference, we also provide appropriate permutation strategies for individual terms in any two-way or three-way ANOVA for the exact test (where possible) and for the approximate test using permutation of residuals.