I do not know much about Haskell, but from what I have read about the mutability of computations (e.g: functions returning functions, complex monads and functions, etc.) it seems like you can do a lot of meta-programming, even at runtime.
I'm not sure what you mean by "mutability" precisely, but it is certainly the case that compiling such an abstract language to efficient machine code is a complicated task. As a starting point, you could read The Implementation of Functional Programming Languages, a book by Simon Peyton-Jones, one of the main people behind Haskell.
For something more recent, there's some commentary on the internals of GHC, the flagship Haskell compiler.
On a more down-to-earth note, if it's just the idea of "functions as values" that you're wondering about, that's old hat--Lisp dialects have been compiling higher-order functions for longer than I've been alive, and even C passes pointers to functions around.
Haskell is actually strongly immutable and strongly static. You can get dynamic behavior and mutability, but the default is immutable data structures and strict referential transparency.
How can Haskell ... compile to machine code ...?
Via this compilation strategy: Implementing Lazy Functional Languages on Stock Hardware
You're using the word 'immutable' in a non-standard way that's confusing people. If some data is immutable, we mean it's not going to change throughout the lifetime of a program. I think what you're asking is this: Haskell allows you to treat functions as first class objects so you can build new functions from old ones on the fly. You're wondering how this could possibly be compiled to machine code when the compiler doesn't know what functions will even exist until runtime. This is a good question.
I'll describe part of an approach that could be used. Not necessarily what any real compiler does. This is just a theoretical idea to give you a feel for how functions apparently built on the fly can be compiled. (Actually, I've used this in a toy compiler.)
Here's a Haskell function
f x = let w = 3*x
g y = w+2*y in g
f is just like you describe. It builds a new function called g that doubles its argument and adds 3*x. It then returns the new function. How can that function be compiled when you don't even know what the function is until x is passed into f?
The compiler can perform a stage called Lambda lifting. It sees that you're locally making a function called g and pulls this out as a global function. There's a catch. We can't make g a global function because it depends on a local value, w. So we pull out g as a global function making w an argument to it:
g' w y = w+2*y
Now the compiler can rewrite f to return g', supplying it with the needed argument:
f' x = let w = 3*x in g' w
You might now ask, "if g' requires 2 arguments, how can we return g' x which only supplies g' with one argument?". Internally the compiler can make what's called a closure. It represents g' w as a structure containing a pair of objects, a pointer (or whatever) to the global function g' and the value w. The compiler can now just go ahead and compile g' as a normal function. I hope you see that we've eliminated any place where a new function could be built. Any time we apply g' w to a second argument, the compiler can spot that it already has the first argument stored, and pass that, and the second argument, into g'.
Again, I'll stress that there are many ways to compile functional code and I've just described one thing you can do. But just showing one way should take away some of the mystery around the fact that it's possible at all. A real compiler might optimise your code in all sorts of ways and eliminate even the need to build a closure. I think the latest C++ standard probably implements the new lambda just as I've described.
I think I understand where you're coming from. When I started learning Haskell I was very much a "how does this compile to assembly language?" person. So after I initially got stuck understanding Haskell I simply stopped, wrote my own compiler for a functional language based on this paper, and then returned to Haskell with a much deeper understanding. SASL isn't compiled at all like Haskell, but it taught me enough to make it easier to understand how Haskell is compiled.