The only correct answer to this is “sometimes”. There are a lot of tricks that functional languages can use to avoid wasting memory. Immutability makes it easier to share data between functions, and even between data structures, since the compiler can guarantee that the data won’t be modified. Functional languages tend to encourage the use of data structures that can be used efficiently as immutable structures (for instance, trees instead of hash tables). If you add laziness into the mix, like many functional languages do, that adds new ways to save memory (it also adds new ways of wasting memory, but I’m not going to go into that).

In functional programming since almost all data structure are immutable, when the state has to change a new structure is created. Does this mean a lot more memory usage?

That depends on the data structure, the exact changes you performed and, in some cases, the optimizer. As one example let’s consider prepending to a list:

list2 = prepend(42, list1) // list2 is now a list that contains 42 followed
                           // by the elements of list1. list1 is unchanged

Here the additional memory requirement is constant – so is the runtime cost of calling prepend. Why? Because prepend simply creates a new cell which has 42 as its head and list1 as its tail. It does not have to copy or otherwise iterate over list2 to achieve this. That is, except for the memory required to store 42, list2 reuses the same memory that is used by list1. Since both lists are immutable, this sharing is perfectly safe.

Similarly, when working with balanced tree structures, most operations require only a logarithmic amount of additional space because everything, but one path of the tree may be shared.

For arrays the situation is a bit different. That’s why, in many FP languages, arrays are not that commonly used. However, if you do something like arr2 = map(f, arr1) and arr1 is never used again after this line, a smart optimizer can actually create code that mutates arr1 instead of creating a new array (without affecting the behavior of the program). In that case the performance will be as in an imperative language of course.

Naive implementations would indeed expose this problem – when you create a new data structure instead of updating an existing one in-place, you have to have some overhead.

Different languages have different ways of dealing with this, and there are a few tricks most of them use.

One strategy is garbage collection. The moment the new structure has been created, or shortly after, references to the old structure go out of scope, and the garbage collector will pick it up instantly or soon enough, depending on the GC algorithm. This means that while there is still an overhead, it is only temporary, and won’t grow linearly with the amount of data.

Another one is picking different kinds of data structures. Where arrays are the go-to list data structure in imperative languages (usually wrapped in some sort of dynamic-reallocation container such as std::vector in C++), functional languages often prefer linked lists. With a linked list, a prepend operation (‘cons’) can reuse the existing list as the new list’s tail, so all that really gets allocated is the new list head. Similar strategies exist for other types of data structures – sets, trees, you name it.

And then there’s lazy evaluation, à la Haskell. The idea is that data structures you create aren’t fully created immediately; instead, they are stored as “thunks” (you can think of these as recipes for constructing the value when it’s needed). Only when the value is needed does the thunk get expanded into an actual value. This means that memory allocation can be deferred until evaluation is necessary, and at that point, several thunks can be combined in one memory allocation.

I only know a little about Clojure and it’s Immutable Data Structures.

Clojure provides a set of immutable lists, vectors, sets and maps.
Since they can’t be changed, ‘adding’ or ‘removing’ something from an
immutable collection means creating a new collection just like the old
one but with the needed change. Persistence is a term used to describe
the property wherein the old version of the collection is still
available after the ‘change’, and that the collection maintains its
performance guarantees for most operations. Specifically, this means
that the new version can’t be created using a full copy, since that
would require linear time. Inevitably, persistent collections are
implemented using linked data structures, so that the new versions can
share structure with the prior version.

Graphically, we can represent something like this:

(def my-list '(1 2 3))

    +---+      +---+      +---+
    | 1 | ---> | 2 | ---> | 3 |
    +---+      +---+      +---+

(def new-list (conj my-list 0))

              +-----------------------------+
    +---+     | +---+      +---+      +---+ |
    | 0 | --->| | 1 | ---> | 2 | ---> | 3 | |
    +---+     | +---+      +---+      +---+ |
              +-----------------------------+

In addition to what has been said in other answers, I would like to mention the Clean programming language, which supports so-called unique types. I do not know this language but I suppose that unique types support some kind of “destructive update”.

In other words, while the semantics of updating a state is that you create a new value from an old one by applying a function, the uniqueness constraint can allow the compiler to reuse data objects internally because it knows that the old value will not be referenced any more in the program after the new value has been produced.

For more details, see e.g. the Clean homepage and this wikipedia article