How can static friction depend on the normal force, but be directed orthogonal to it? According to my understanding:


*

*two orthogonal forces aren't related and two orthogonal vectors don't affect each other

*the force of static friction $F_s$ depends on the normal force $F_n$, so $$F_s = \mu_s F_n$$ ($\mu_s$ being the static friction coefficient).


If these two are correct, how can the force of static friction, determined by a force normal to the surface, be directed tangential to the surface and orthogonal to the normal force?
 A: Re. "two orthogonal forces aren't related and two orthogonal vectors don't affect each other"
Your equation $F_s = \mu_s F_n$ is not a vector equation.  $F_s$ and $F_n$ are both scalars.  If they were vectors, and were orthogonal, the equation would be mathematically incorrect.
A: There are two different things here that need to be firmed up:


*

*The first is the notion that "two orthogonal vectors don't affect each other". I am not sure what is meant by this statement, but I suppose you are thinking how that adding one of a pair of orthogonal vectors to a given vector does not affect the component of that vector in the direction of the other vector. The trick here is that the normal and frictional forces are two separate force vectors, that happen to be orthogonal, and both get added to produce the total force ($\mathbf{F}_\mathrm{tot} = \sum_i \mathbf{F}_i$). Moreover, the correct relationship between the normal and frictional forces is that the latter is a function of the former: $\mathbf{F}_\mathrm{fric} = \mathbf{f}(\mathbf{F}_\mathrm{norm})$. If one is a function of the other then of course one will contribute to the other, because they are now mathematically linked, whether they be orthogonal or not.

*The second is relating to why, physically, that there should be this dependence. To understand this, you have to understand how the friction force arises microscopically. It occurs because that tiny bonds form between atoms in the surfaces. You may have wondered why that, when you break, say, a piece of chalk, you cannot make the two pieces meld back together into a single chalk, and you might wonder how to reconcile this with the notion there are attractive forces between atoms. The reason why is actually that they do try to meld together, but they can't because the surfaces don't match up absolutely perfectly on a microscopic scale. Yet to a small extent, they do - tiny protrusions on one surface will meet with those on the other and they will form bonds - instantly! The reason the pieces don't meld together entirely is that only a few actually stick as the surfaces are not perfectly geometrically compatible. This also happens when you have, say, one brick sitting on another, and the "friction" that is holding the two in place is actually these bonds! If you press the bricks together more tightly (which corresponds to increasing the normal forces from each other), you ever-so-slightly deform their surfaces and flatten out some of the microscopic projections so that more of each one comes into contact with the other, and also, by doing so bring the surfaces closer and new projections into contact. This causes the bonds to proliferate and so the frictional hold to increase. "Breaking" the friction - causing the bricks to begin sliding with enough lateral force - corresponds to providing enough force to break these bonds.


And as you might guess, given the second point, friction is actually very complicated, and so you should wonder "well then why can we describe it by such a cute linear equation"? And you'd be right to be suspicious. The simple linear equation $F_\mathrm{fric} = \mu F_\mathrm{norm}$ is just a simplistic model. It works okay in some limited circumstances and as long as you don't need too much precision. Realistically, friction can indeed be much more complicated, and is best figured out by empirical experiment and measurement, than derived from theory.
Moreover, if you guessed that the effects described, since they involve things bending and breaking, actually modify or damage the surface, you're right! We call this "wear". It's why that sandpaper works, it's why bearings need to be periodically replaced, it's why a nail file works, it's why that if you fall on a road while moving you get road rash, part of why clothes eventually fray from repeated rubbing and use, etc.
Finally, if you think that something interesting might happen if you did have absolutely perfectly geometrically compatible surfaces, e.g. two pieces of metal of the same type, hyper-pure, and surfaces totally flat down to not even a single atom's deviation, you'd be right! Indeed, upon contact the same thing occurs but now over the entire surface: every part bonds, and the two pieces of metal literally merge with no effort into a single contiguous piece, exactly as you'd expect from the notion of attractive forces! It's called "contact welding". It also needs to be done in vacuum, because any air molecules in between will still frustrate the surfaces from perfectly contacting each other. Welds formed this way can be some of the best you can get, but it's very limited in applicability precisely because of the geometric compatibility requirements. Typically one will still need some applied pressure to get a good weld because of this, to deform the surfaces the "last bit of the way" and make them contact each other completely.
A: Two orthogonal vectors $\vec a$ and $\vec a_{_{\perp}}$ may not be additively related, sure. A linear combination is not possible: $$\vec a\neq k\vec a_{_{\perp}}$$
But we could easily imagine a simple linear function that did this:
$$f(\vec a)=k\vec a_{_{\perp}}$$
Imagine that a rough surface is such a function - that the physical phenomenon of "friction creation" is such a function. A function that takes the vector and converts it into a perpendicular version of itself - times some constant.
The resulting vector $\vec a_{_{\perp}}$ happens to be $k$ times shorter than the original $\vec a$, so:
$$|\vec a|=|k \vec a_{_{\perp}}|\\
a=k a_{_{\perp}}$$
This does not say that vector $\vec a$ equals vector $k \vec a_{_{\perp}}$, only that their magnitudes are equal. And now imagine that we see this behaviour in the physical world and that we rename the parameters involved and write:
$$F=\mu n$$
Again, not a vector relationship. It would be wrong to write: $\vec F=\mu \vec n$. Rather, just a scalar relationship.

So, mathematically, nothing is wrong with the formula: $F=\mu n$. The only question left is why the physical world happens to behave like this?
Imagine a rough surface as full of peaks and valleys at the microscale (microscopy image here from this source). When two surfaces like that come into contact, one will "fit into" the other by having it's peaks falling into the opposite valleys etc. In this fitted position, the touching material may adhere with different weak or strong bondings.
In order to start sliding one surface over the other, you must rip that surface free from the other. You must break the adhesion bonds and must lift the surface peaks out of the valleys. This requires some force. We call that force friction.
Naturally, the harder the surfaces are pressed together - the larger the downwards force $\vec n$ - the tougher it is to rip them apart again, so the larger is $\vec F$. Those two forces happen to be proportional in magnitude, because all other factors (like contact area, speed etc) happen to cancel out.
At very high normal forces or very soft materials, parameters like the contact area will not cancel out. In those cases, the proportionality doesn't hold and $F\neq \mu n$. The relationship $F= \mu n$ counts for small normal forces.

NB: Note that that there is a difference between static and kinetic friction. When you write static friction as $F_s=cF_n$, the be aware that the general low-normal-force relationship should rather be written as:
$$F_s\leq cF_n$$
This relationship only turns into $F_s=cF_n$ right at the limit before the static friction cannot hold anymore.
For low-normal-force kinetic friction the equality is always true, though:
$$F_k=c_kF_n$$
A: The 'force of static friction' is not a vector per se, it is a limiting
value of the tangential force that can be applied without breaking
the bond between 'two objects' when those objects are in contact (basically,
glued together with a very weak glue).   It is a scalar, not a vector.
So, despite the fact that a normal force does not provide any symmetry
breaking to generate a 'friction force'  tangential vector
direction, it does affect the surface/surface bond strength, in shear
stress conditions.
The consequences of this, include the impossibility of dissipating energy with
the static friction: when taking a dot product of displacement and
force, the displacement implies sliding friction.   That is why
ball bearings (which roll, but do not slide) are so energy
efficient.   Also, it means that the best ball bearing lubricants are
very different from sliding-bearing lubricants.
A: 
two orthogonal forces aren't related and two orthogonal vectors don't affect each other

This wording isn't very precise. I can think of some ways orthogonal vectors can be related. For example, If I apply a force $\mathbf F$ tangent to a disk at position $\mathbf r$ relative to the center, then $\mathbf r\times\mathbf F=\mathbf\tau$ gives me the torque $\mathbf\tau$ about the center of the disk, and all three mentioned vectors are orthogonal. I would say these vectors are related via the cross product, and both $\mathbf F$ and $\mathbf r$ effect the torque $\mathbf\tau$. To drive this home further, we have, for example,
$$\tau_x=r_yF_z-r_zF_y$$
So the x-component of the torque is related to the other two components of the other vectors (Similar expressions can be written out for the other components of the torque).
I think what this statement comes from is what introductory physics students hear about projectile motion: horizonal forces don't influence vertical motion, and vice versa. This is true, because $F_i=ma_i$, where the subscript $i$ represents a component ($x$, $y$, or $z$) of the vectors. This is very helpful for problems where we break up the forces into components, but as we have seen above, this doesn't mean that orthogonal vector components of different vectors can't be related.
So onto friction$^*$, if we have an object on a horizonal surface, there really is nothing wrong with having
$$f_x=\mu N_y$$
Or, if we want to be more general,
$$f_{parallel}=\mu N_{perpendicular}$$
But since friction is always parallel to the surface, and the normal force is always perpendicular to the surface, we just write
$$f=\mu N$$
No problem at all. Note, this is not the same thing as writing $\mathbf f=\mu\mathbf N$, which is not a true equation and might also be adding to your confusion. If you want to use the vectors, you would write $\mathbf f=\mu N\mathbf{\hat f}$ where $\mathbf{\hat f}$ is parallel to the surface and $N$ is the magnitude of the normal force.

$^*$ Unlike other answers that go into detail about why this simple friction model makes sense (and a lot of these answers seem repeat information already posted in answers before them, but I digress), I will not discuss the microscopic details here. Your question is purely about the vectors and not about the physical mechanics behind it.
A: Given two surfaces which on the microscopic scale are "rough" you might expect that pushing them together harder (the normal reaction forces) would make it more difficult for them to slip relative to one another (the tangential frictional forces) as it more difficult to move the "hills" on one of the surfaces across the "valleys" and "hills"  on the surface.
