Have I understood correctly that in (most? some?) multiple dispatch languages each method gets added to the function at some point in time of program's execution.
Can I then conclude that multiple dispatch as a feature forces functions to be mutable?
Is there a multiple dispatch language, where all methods are attached to a (generic)function together (at load time?), so that it's not possible to see the function in different states at different points in time?
at some point in time of program's execution.
In Common Lisp the methods get added/replaced when the method definitions are executed - for a compiled system this is typically at load-time of the compiled code - not necessarily during the program's execution.
Remember, that Common Lisp has an object system (CLOS, the Common Lisp Object System), which is defined by its behaviour. It's slightly different from a language or a language extension.
Common Lisp allows runtime modification of the object system. For example also adding/removing/replacing methods.
Common Lisp also may combine more than one applicable method into an effective method, which then gets executed. Typical example: all applicable :before methods and the most specific applicable primary method will be combined into one effective method.
There exist extensions for CLOS in some implementations, which seal a generic function against changes.
For a longer treatment of the idea of an object system see: The Structure of a Programming Language Revolution by Richard P. Gabriel.