Копируется ли состояние при каждой операции над монадой состояния в Haskell?
Копируется, только надо учитывать ленивость и чистоту Хаскеля.
Если взять обычный список и класть ему в голову - ничего не надо будет копировать, так как добавление головы не требует копирования хвоста, новый список будет просто ссылаться на хвост. Удаление головы (т.е. взятие хвоста) тоже не требует создавать копий.
Если же вы будете в качестве состояния использовать какой-либо строгий тип данных, да с unboxed членами, тот да, будет копироваться.
Надо учитывать так же и другую вещь: накопление thunk'ов. Например, если состояние - это число, и вы миллион раз сделаете modify (+1), по факту там будет лежать отложенное вычисление на миллион прибавлений единиц, что будет кушать память. Потому есть строгая монада state, а также modify', который форсирует применение переданной функции.
Пример, что вы привели на питоне -- это stack, а не state.
Монада State не предоставляет функциональности стека, она лишь предоставляет возможность хранения некой переменной. С точки зрения человека с головой набитой императивными тараканами это выглядит как полное копирование. Тем ни менее это не так и все зависит от программиста, нужно ли ему таскать за собой весь список или нет решает сам программист.
Например, stack-пример, приведенный выше можно реализовать (используя классическую императивную реализацию) с помощью State монады так: import Control.Monad.State

pop :: State [a] a
pop = do
  h <- head <$> get
  modify tail
  return h

push :: a -> State [a] ()
push = modify . (:)

print $ runState (mapM_ push [1 :: Int ,2,3,4]>>pop) []
Тем ни менее ленивые вычисления с слабые на голову конструкторы сильно меняют логику выполнения программы, если смотреть с классической императивной позиции.