When you define a function f, you are (a) applying Set or SetDelayed to a pattern, (b) creating a rule, (c) associating the rule with a symbol (f), and (d) storing that in DownValues (usually).

FullForm[Hold[f[x_] := x^2]]
(* Hold[SetDelayed[f[Pattern[x, Blank[]]], Power[x, 2]]] *)

f[x_] := x^2
DownValues@f
(* {HoldPattern[f[x_]] :> x^2} *)

###First question: is it true that "everything in Mathematica is ultimately stored as a rule?"

No: for example 2 is not a rule. It's just 2. So not everything is a rule, just functions. Everything is an expression, ... some expressions (as a side-effect) create and store rules in DownValues.

###Second question: does Mathematica "gloss over" these rules by representing them as functions? Yes and no. They give you a glossy shortcut for input:

f[x_] := x^2

instead of requiring you to write something like

AppendTo[Downvalues[f], f[x_] :> x^2]

There was one misunderstanding in your question; you asked about the output of

FullForm[f[x]]

This is not showing you the definition of the function f. It is showing you the result of applying f to x. See the following:

FullForm[f[2]]
(* 4 *)

If you want to see the definition of f you should either use Information (which is glossy and not very useful) or DownValues which contains what you're after.

###Third question: does the by value/by reference question have any when you "pass" a value to a Mathematica function? Work on the assumption that Mathematica is pretty smart "under the hood" about pass by value/ pass by reference.

When you define a function f, you are (a) applying Set or SetDelayed to a pattern, (b) creating a rule, (c) associating the rule with a symbol (f), and (d) storing that in DownValues (usually).

FullForm[Hold[f[x_] := x^2]]
(* Hold[SetDelayed[f[Pattern[x, Blank[]]], Power[x, 2]]] *)

f[x_] := x^2
DownValues@f
(* {HoldPattern[f[x_]] :> x^2} *)

###First question: is it true that "everything in Mathematica is ultimately stored as a rule?"

No: for example 2 is not a rule. It's just 2. So not everything is a rule, just functions. Everything is an expression, ... some expressions (as a side-effect) create and store rules in DownValues.

###Second question: does Mathematica "gloss over" these rules by representing them as functions? Yes and no. They give you a glossy shortcut for input:

f[x_] := x^2

instead of requiring you to write something like

AppendTo[DownValues[f], HoldPattern[f[x_]] :> x^2]

There was one misunderstanding in your question; you asked about the output of

FullForm[f[x]]

This is not showing you the definition of the function f. It is showing you the result of applying f to x. See the following:

FullForm[f[2]]
(* 4 *)

If you want to see the definition of f you should either use Information (which is glossy and not very useful) or DownValues which contains what you're after.

###Third question: does the by value/by reference question have any when you "pass" a value to a Mathematica function? Work on the assumption that Mathematica is pretty smart "under the hood" about pass by value/ pass by reference.