Or, are the interpreted each time they are executed? If not compiled (JIT?) then how much slower is their execution than native code?
Python is by default an interpreted language. Blender bundles and uses the default python runtime (CPython), ans therefore python code in blender is interpreted.
However there is a catch. Most of Blender's API is actually written in native code (C) and is then exposed to the Python runtime through generated bindings.
Relative performance is trickier, as this is dependent on many many factors. And there are other issues here as well, in particular the GIL, which prevents the CPython interpreter from being truly multithreaded. Efficient use of the Blender API and the Numpy library (bundled with Blender) can bring most performance issues to acceptable levels. It is best to start with those anyway, and only look at other alternatives when you actually run into issues (i.e. avoid premature optimisation). You may find that the main performance bottlenecks are things other than code execution speed anyway (e.g. file handling).
As already explained, while your script is interpreted, much of the work may be done with code already compiled into blender.
However there are other alternatives, a blender addon is a python module, it can be written is C/C++ and compiled the same as any other python module. There are some requirements to being a blender addon, such as having a bl_info dictionary and register/unregister methods.
An easy method to make a compiled binary addon, would be to use Cython, which will turn python code into C/C++ that is then compiled. For examples, have a look at Cubesurfer or Animation Nodes. You can also use cython as a starting point to generate the framework that you then fill in or link to your C/C++ code.