Where is the "document.getElementById()" function stored?

The method is exposed as part of the DocumentPrototype object, accessible under window.Document.prototype:

The window.document instance only inherits it from the Document class.

console.log( Document.prototype.getElementById );

Document.prototype.getElementById = (val) => 'gotcha ' + val;
console.log( document.getElementById( 'foo' ) );

Now, the native function being a native function, browsers don't give us access to it, and certainly, it's not even a JS function.

It will depend on native code (probably in C++) that is part of the browser. You could search for getElementById in the source code of a web browser to look at it.

JavaScript is an interpreted language; every web browser has a JavaScript interpreter. When you write JavaScript yourself, you can define methods on objects. However, what you can't do from JavaScript is write native methods; these have to be provided as part of the browser. If you try to print the source of these functions from JavaScript with toSource, you see a note indicating that these functions are in fact native.

console.log((function(){}).toSource());
console.log(alert.toSource());

The point of native code is that it can access things which are deliberately inaccessible to JS code. For example, events can be scheduled with window.setTimeout despite there being absolutely no way to implement setTimeout in plain JS. Browsers have huge codebases, none of which I'm familiar with, so it's difficult to express in a short answer exactly they work. However, to give you a taste of their workings, Chromium's element.cc contains implementations for familiar methods like setAttribute and in container_node.cc there is an implementation of getElementById.