That's not a particularly great example though because 99 bottles of beer is not a particularly stateful computation. You could easily do it without state at all like this: https://gist.github.com/lgastako/2e7dfd6b1118bb408ff114a4be4...
On the other hand this blog post http://www.haskellforall.com/2013/05/program-imperatively-us... demonstrates how one of the bits of Haskell that some people find complex (lenses) can be used together with the state monad to provide an "imperative-like" experience that's even nicer than most imperative languages.
There were other examples, but figuring out how to deal with state is the most arcane and mystical aspect of haskell.
Is it just me, or is the linked example messed up in all sorts of ways, even ignoring the use of monads and transformers? Looks like a novice trying to code in fancy ways.
For instance, it defines a Beer datatype, yet stores a plain Int in the state, then casts it to Beer only to use a custom pretty printer, instead of creating a verse :: Int -> String, or verse :: Beer -> String function.
99 bottles of beer with state monads gets at some of the challenge for the neophyte:
http://www.99-bottles-of-beer.net/language-haskell-1360.html
Look at the struggle going on to deal with a "simple" piece of state.