C# and all the other languages belonging to the .NET framework are interpreted languages. They are pseudo-compiled, not truly compiled (like C). The bytecode of the .NET framework is called Common Intermediate Language (CIL).
The interpreter (sometimes known as "virtual machine") for the Common Intermediate Language is the .NET Common Language Runtime on Windows and Mono on Linux. Therefore, C# applications won't run "native" (i.e. without an interpreter), not even on Windows.
Probably what surprises you is that Mono is not installed by default on some Linux distributions, while the .NET runtime is.
Anyhow, you can write applications in C# that are nicely integrated with Ubuntu. An example is Tomboy.
There's also an another language, similar to C#, developed by the GNOME project, which is Vala. Vala is translated into C, which is itself compiled, so it will run "native". Because Vala was built by GNOME developers for GNOME developers, it is extremely easy to integrate with the GNOME desktop environment.