Most so-called immutable languages provide a back door that allows you to escape from the immutability amd use mutable data structures. For example, Haskell provides the ST monad and the ability to store mutable data with the IO monad. It also has a function "unsafePerformIO" which you can use to execute IO operations in a context that is not declared to use the IO monad. You can use these basic building blocks to perform memoization (and as such an implementation should be provably referentially transparent, it is not unsafe to do so (despite the stern-sounding warning in the function name)).
I can therefore see there possible signatures for a memoize function:
mwmoizeST :: (a -> b) -> a -> ST s b
memoizeIO :: (a -> b) -> a -> IO b
memoizeUmsafeIO :: (a -> b) -> a -> b
All could be useful in different circumstances.
Other similar languages provide similar escape hatches - they have to, as sometimes a mutable structure is the only way to achieve satisfactory performance.