So

1) How can I use transformers instead of the mtl? This is in no
tutorial, and searchinf for "mtl" on the haskell wiki yields no
result at all.

> cabal install transformers (you need cabal-install to do this... consult #haskell if confused)
perhaps: > ghc-pkg hide mtl (I think mtl and transformers fight over the Control.Monad module)

Then import Control.Monad.Trans.State instead of Control.Monad.State. All else should be well, if I am not forgetting something.

2) What should be the Haskell98-compatible type signature for my play2 function, instead of (MonadState [a] m, Eq a) =>
a -> m Bool ?

That depends on the monad library. In transformers it would be:

(Monad m, Eq a) => a -> StateT [a] m Bool

State s is just a type synonym for StateT s Identity, so this works for State as well.

Luke