How do functional programming languages work?

If functional programming languages cannot save any state, how do they do some simple stuff like reading input from a user (I mean how do they "store" it), or storing any data for that matter?

As you gathered, functional programming doesn't have state—but that doesn't mean it can't store data. The difference is that if I write a (Haskell) statement along the lines of

let x = func value 3.14 20 "random"
in ...

I am guaranteed that the value of x is always the same in the ...: nothing can possibly change it. Similarly, if I have a function f :: String -> Integer (a function taking a string and returning an integer), I can be sure that f will not modify its argument, or change any global variables, or write data to a file, and so on. As sepp2k said in a comment above, this non-mutability is really helpful for reasoning about programs: you write functions which fold, spindle, and mutilate your data, returning new copies so you can chain them together, and you can be sure that none of those function calls can do anything "harmful". You know that x is always x, and you don't have to worry that somebody wrote x := foo bar somewhere in between the declaration of x and its use, because that's impossible.

Now, what if I want to read input from a user? As KennyTM said, the idea is that an impure function is a pure function that's passed the entire world as an argument, and returns both its result and the world. Of course, you don't want to actually do this: for one thing, it's horribly clunky, and for another, what happens if I reuse the same world object? So this gets abstracted somehow. Haskell handles it with the IO type:

main :: IO ()
main = do str <- getLine
          let no = fst . head $ reads str :: Integer
          ...

This tells us that main is an IO action which returns nothing; executing this action is what it means to run a Haskell program. The rule is that IO types can never escape an IO action; in this context, we introduce that action using do. Thus, getLine returns an IO String, which can be thought of in two ways: first, as an action which, when run, produces a string; second, as a string that's "tainted" by IO since it was obtained impurely. The first is more correct, but the second can be more helpful. The <- takes the String out of the IO String and stores it in str—but since we're in an IO action, we'll have to wrap it back up, so it can't "escape". The next line attempts to read an integer (reads) and grabs the first successful match (fst . head); this is all pure (no IO), so we give it a name with let no = .... We can then use both no and str in the .... We've thus stored impure data (from getLine into str) and pure data (let no = ...).

This mechanism for working with IO is very powerful: it lets you separate the pure, algorithmic part of your program from the impure, user-interaction side, and enforce this at the type level. Your minimumSpanningTree function can't possibly change something somewhere else in your code, or write a message to your user, and so on. It's safe.

This is all you need to know to use IO in Haskell; if that's all you want, you can stop here. But if you want to understand why that works, keep reading. (And note that this stuff will be specific to Haskell—other languages may choose a different implementation.)

So this probably seemed like a bit of a cheat, somehow adding impurity to pure Haskell. But it isn't—it turns out that we can implement the IO type entirely within pure Haskell (as long as we're given the RealWorld). The idea is this: an IO action IO type is the same as a function RealWorld -> (type, RealWorld), which takes the real world and returns both an object of type type and the modified RealWorld. We then define a couple functions so we can use this type without going insane:

return :: a -> IO a
return a = \rw -> (a,rw)

(>>=) :: IO a -> (a -> IO b) -> IO b
ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw'

The first one allows us to talk about IO actions which don't do anything: return 3 is an IO action which doesn't query the real world and just returns 3. The >>= operator, pronounced "bind", allow us to run IO actions. It extracts the value from the IO action, passes it and the real world through the function, and returns the resulting IO action. Note that >>= enforces our rule that the results of IO actions never be allowed to escape.

We can then turn the above main into the following ordinary set of function applications:

main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ...

The Haskell runtime jump-starts main with the initial RealWorld, and we're set! Everything's pure, it just has a fancy syntax.

[Edit: As @Conal points out, this is not actually what Haskell uses to do IO. This model breaks if you add concurrency, or indeed any way for the world to change in the middle of an IO action, so it would be impossible for Haskell to use this model. It is accurate only for sequential computation. Thus, it may be that Haskell's IO is a bit of a dodge; even if it isn't, it's certainly not quite this elegant. Per @Conal's observation, see what Simon Peyton-Jones says in Tackling the Awkward Squad [pdf], section 3.1; he presents what might amount to an alternative model along these lines, but then drops it for its complexity and takes a different tack.]

Again, this explains (pretty much) how IO, and mutability in general, works in Haskell; if this is all you want to know, you can stop reading here. If you want one last dose of theory, keep reading—but remember, at this point, we've gone really far afield from your question!

So the one last thing: it turns out this structure—a parametric type with return and >>=— is very general; it's called a monad, and the do notation, return, and >>= work with any of them. As you saw here, monads aren't magical; all that's magical is that do blocks turn into function calls. The RealWorld type is the only place we see any magic. Types like [], the list constructor, are also monads, and they have nothing to do with impure code.

You now know (almost) everything about the concept of a monad (except a few laws that must be satisfied and the formal mathematical definition), but you lack the intuition. There are a ridiculous number of monad tutorials online; I like this one, but you have options. However, this probably won't help you; the only real way to get the intuition is via a combination of using them and reading a couple tutorials at the right time.

However, you don't need that intuition to understand IO. Understanding monads in full generality is icing on the cake, but you can use IO right now. You could use it after I showed you the first main function. You can even treat IO code as though it was in an impure language! But remember that there's an underlying functional representation: nobody's cheating.

(PS: Sorry about the length. I went a little far afield.)

Plenty of good answers here, but they are long. I'm going to try to give a helpful short answer:

• Functional languages put state in the same places that C does: in named variables and in objects allocated on the heap. The differences are that:

  • In a functional language, a "variable" gets its initial value when it comes into scope (through a function call or let-binding), and that value doesn't change afterward. Similarly, an object allocated on the heap is immediately initialized with the values of all its fields, which don't change thereafter.

  • "Changes of state" handled not by mutating existing variables or objects but by binding new variables or allocating new objects.

• IO works by a trick. A side-effecting computation that produces a string is described by a function that takes a World as argument, and returns a pair containing the string and a new World. The World includes the contents of all disk drives, the history of every network packet ever sent or received, the color of each pixel on the screen, and stuff like that. The key to the trick is that access to the World is carefully restricted so that

  • No program can make a copy of the World (where would you put it?)

  • No program can throw away the World

  Using this trick makes it possible for there to be one, unique World whose state evolves over time. The language run-time system, which is not written in a functional language, implement a side-effecting computation by updating the unique World in place instead of returning a new one.

  This trick is beautifully explained by Simon Peyton Jones and Phil Wadler in their landmark paper "Imperative Functional Programming".