This is perfectly simple. You just need a suitable test statistic! One thing you need is that the test statistic will behave differently when the alternative is true that when the null is true.
There's a variety of ways to approach it, but you may find with a little thought that they tell you the same thing.
a) One approach is to take the difference between the count above $m_0$ and the count $\leq m_0$. This will tend to be close to $0$ when $H_0$ is true (and the distribution is continuous) and tend not to be close to $0$ when $H_0$ is false. You might then choose to have your rejection region be the cases when the absolute value of the test statistic is largest.
b) You could just count how many sample values are $\leq m_0$ (call this $X$ say). If the null is true and the distribution is continuous this should be close to $n/2$. Otherwise it might tend to be larger or smaller. You need some way to chose which permutations in those two tails are at least as extreme as each other; if you use distance from $n/2$ that would be the same as using $T=|X-n/2|$ as a test statistic.
[There are several other ways you could do it]
So what do you randomize here? If the null is true, each observation is equally likely to be above $m_0$ (for which its contribution to the difference in counts will be +1) as below (for which its contribution to the difference in counts will be -1). Which is to say you randomly assign each observation to be either in the group "above the median" or "below the median" ("toss a coin", in effect). There are a bunch of ways to do this as well.
If instead of the difference in counts above and below you used the count below $m_0$ then the contributions to the count would be 0 and 1 with equal probability, so for each observation you'd generate a random set of 0's and 1's (and this is where the equivalence to the sign test should now be completely plain).
Hopefully that's enough for you to begin (as well as to see why it should give you the same information as a sign test does).
