Given immutability (which is often encouraged and said to be one of building blocks of functional programming) and CQS (which says that commands should not return a value other than void/unit), how do these work together?
There are no commands in functional programming. Period.
A function's result can only depend on its arguments, and it must be the same every time you call the function with the same arguments. There can be no mutation and no side-effects. Functions must be referentially transparent, which means that I can always replace the function application with its result anywhere and everywhere in the program without changing the meaning of the program. (In particular, this means that if I have a procedure that returns
void (i.e. nothing), I can replace it with nothing everywhere, which obviously will change the meaning of the program, and thus such a procedure cannot exist in functional programming.)
Of course, something command-like must still be achievable, otherwise your programs would be pretty boring. As Simon Peyton-Jones ones said during an introduction to Haskell, if your program has no side-effects, it cannot print a result, it cannot ask for input, it cannot interact with the network or the file system, all it does is heat up the CPU, after which someone from the audience interjected that heating up the CPU is also a side-effect, so, technically speaking, if you want your program to have no side-effects, you cannot even run it. Clearly, that is ridiculous.
So, side-effects have to be modeled somehow.
One way to do this, is to imagine that you can somehow describe the state of the entire universe in a datastructure and then pass an instance of that datastructure describing the current state of the world into a function, and the function then returns a new instance of that datastructure describing the new state of the world. Of course, this cannot literally work, describing the state of the world requires at least as much memory as the entire world has. It's a conceptual model.
There's a slight problem: the function could pass the old state of the world on to another function, for example, now there are two functions which have the same state of the world, and both of them could return a different new state of the world. Or, a function could hold on to the old state of the world, and later return it back, effectively time-traveling into the past. Of course, this must be somehow prohibited. One solution would be linear types, which are types that ensure that its values are used only once. Clean does this, it has World types, which are a special kind of linear types for such world values.
In Haskell, all side-effects must take place in a monad. Monads are a way of augmenting computation with additional structure. You can imagine it as the monad threading the world value described above through the different functions but without ever actually directly exposing the value to the functions. (In reality, once you have monadic I/O, you don't actually need the world value any more, the monad itself provides the structure for side-effects.) Earlier attempts at modeling I/O in Haskell included I/O based on lazy streams and continuation-based I/O, which also work, but monadic I/O was found to be easiest to work with.
In all these different models, side-effects will always show up in the types of side-effecting functions. IOW, your commands are now functions which return, takes an argument, or both, a value of a side-effecting type.
A nice side-effect (hah!) of this is that different kinds of side-effects can get their own types, instead of having a catch-all "this is a side-effect" type. For example, in Haskell, there is the well-known
IO type, which basically says "anything can happen". But there are also types like
Reader (reads global state, an OO example would be a global singleton configuration object that is dependency-injected),
Writer (writes global state, e.g. a logger, again, typically solved in OO with a global singleton logger object that gets injected),
State (mutable shared state, but no other kind of side-effect),
STM (Software Transactional Memory, like
State but transactional for parallelism).
The "separation" portion of CQS is achieved using the type system. Commands simply have types that are incompatible with queries. I.e. a "command" which changes some global integer will have
State Int somewhere in its type, a command which prints an integer will have type
Int -> IO Int and so on.