Your app is compiled from MSIL to native on MS's servers if it's like Windows Phone. I think they can recompile everything if a dependency changes for example and push a new app version for you.
It happens on your local machine. There's a checkbox to enable / disable it.
It happens in both places. You can (and should) test with .NET Native enabled on your local machine. You still upload IL to the Windows Store, and the final native compilation is done there. The Windows Store uses the same .NET Native SDK as ships with Visual Studio.