How MonadState could potentially look, using DefaultSignatures and type equality constraints.

MonadState.hs

{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}

import Control.Monad.Trans.Class
import qualified Control.Monad.Trans.State as State
import Control.Monad.Trans.Identity (IdentityT)
import Control.Monad.Trans.Reader (ReaderT)
import Control.Monad.Trans.Writer (WriterT)
import Control.Monad.Trans.State (StateT)
import Control.Monad.Trans.Maybe (MaybeT)
import Control.Monad.Trans.Except (ExceptT)
import Control.Monad.Trans.Cont (ContT)

class Monad m => MonadState s m | m -> s where
  get :: m s
  put :: s -> m ()
  -- These implementations work when the monad is some transformer applied to a monad
  -- which is already an instance of MonadState s.
  default get :: (MonadTrans t, m ~ t n, MonadState s n) => m s
  get = lift get
  default put :: (MonadTrans t, m ~ t n, MonadState s n) => s -> m ()
  put s = lift (put s)

-- This instance uses actual implementations of the operations
instance Monad m => MonadState s (StateT s m) where
  get = State.get
  put = State.put

-- These instances use the default lifting instance behaviour from the class declaration, so
-- they can simply be blank. We only have to point out that we want them at all.
instance MonadState s m => MonadState s (IdentityT m)
instance MonadState s m => MonadState s (ReaderT e m)
instance (MonadState s m, Monoid w) => MonadState s (WriterT w m)
instance MonadState s m => MonadState s (MaybeT m)
instance MonadState s m => MonadState s (ExceptT e m)
instance MonadState s m => MonadState s (ContT r m)