(Don't have much time now so I'll answer briefly and then expand later)
Say that we are considering a binary classification problem and have a training set of $m$ class 1 samples and $n$ class 2 samples. A permutation test for feature selection looks at each feature individually. A test statistic $\theta$, such as information gain or the normalized difference between the means, is calculated for the feature. The data for the feature is then randomly permuted and partitioned into two sets, one of size $m$ and one of size $n$. The test statistic $\theta_p$ is then calculated based on this new partition $p$. Depending on the computational complexity of the problem, this is then repeated over all possible partitions of the feature into two sets of order $m$ and $n$, or a random subset of these.
Now that we have established a distribution over $\theta_p$, we calculate the p-value that the observed test statistic $\theta$ arose from a random partition of the feature. The null hypothesis is that samples from each class come from the same underlying distribution (the feature is irrelevant).
This process is repeated over all features, and then the subset of features used for classification can be selected in two ways:
- The $N$ features with the lowest p-values
- All features with a p-value$<\epsilon$