Consider the getLine function:

  getLine :: IO String

getLine takes nothing as its input--not the state of the world, or whatever, but nothing--and produces a string that's inside an IO monad. To all appearances, it's an impure function. But because the String is inside a box (so to speak) you can't peek at it--instead, you can only give it to another function, provided that function also returns a box you can't peek into.

In effect, this creates two classes of functions. Some, like getLine, can have side effects, generate random values, look into other boxes, whatever. These are technically "pure" in a mathematical sense since their outputs are always inside identical boxes, but in practice they behave just like impure functions, and you reason about them the same way. The rest have more restricted capabilities, and because their values aren't inside boxes, the compiler can verify that they return distinct values in a pure manner.

So, for an extreme example, consider this function:

  foo (x) { x++; return x; }

In Haskell foo would return "IO Int," which means the "Int" may be produced impurely. Actually, the integer is produced in a pure manner, so it would be fine for foo to return a plain Int. But the way Haskell determines purity is too crude to figure that out: all it knows is that foo depends on a mutation, which may make the output impure. Impurity is contagious, so foo "catches" it from ++ and thus has to put its output in a box.

Hence, the typical description of pure functional programming as "functions only transform inputs to outputs" is only true in the most trivial mathematical sense, and has no practical import. Pure functional programming really means writing a crude proof that a certain subset of your program is pure, and the compiler checking the proof for you.

(Disclaimer: I understand that this is a very vague high-level description of monads, that monads can work in other ways and do many other things, and that purely functional languages can handle state/side effects/etc. in other ways. It's a complex issue and I'm just trying to convey the way that it usually works in practice.)