Is a "Blender Game Engine" game built into native code or something higher level like python? When building a game made with the Blender Game Engine, is the resulting program native? If not what is it compiled into?
The binary that executes the game (i.e. Blenderplayer) is native code compiled from a combination of C and C++. I don't think there are any Python based Blender operators that run when you play a game. So yes it's completely 'native'.

If you choose to extend the game with Python script, which will be interpreted at runtime with a Python 3.3 (as of Blender 2.70) interpreter, then it will be a mix of 'native' component and interpreted scripts.

Unless you are doing some serious Python coding, the performance overhead of Python is very small.