Earlier quoted context omitted.
The C# compiler is written in C#, so you can use it anywhere with a .NET runtime. Microsoft doesn't ship a .NET runtime for Linux, so you'll have to use Mono, but if your app is compatible with Mono, you're good to go!
How does something like this happen? How can you write a compiler in the language that it is supposed to be compiling?
Bootstrapping a compiler from nothing is harder and involves a lot of incremental steps. http://en.wikipedia.org/wiki/Bootstrapping_(compilers)