As far as I know, we do not write the assemblers or compilers in machine language, so how do we add these programs to the new machine so that it can run programs in high-level language?
As a matter of fact we do, at least if there is no other development chain available for cross-compilation. The first modern computers didn't have one, so yes, people wrote assemblers in machine language, then compilers in assembly language, and finally application programs in higher-level languages. Google "bootstrapping" for more information.
Today, of course, it is very rare that no cross-compiling development chain is available, since there are multiple free or almost-free compiler kits out there that have portability as one of their main goals. In fact, it's unlikely that we will ever go back to the times when new machines have no option to cross-develop anything! The chain of program-transforming programs goes back in history all the way to the beginning of compilers, much like all life today is ultimately descended from the same cells eons ago, and losing it would be a catastrophe similar to killing off all higher life and having to let nature redevelop it from single-cell organisms. But at least in principle, yes, compilers have to be arduously implemented at a level below the one they're supposed to work with.