How does the COM of a rigid body always move as if only external forces influence it? There's this example in my physics textbook:

It seems to suggest that the resultant of all external forces acting on a body tells you how the COM of the body is going to move. Now, I understand the mathematical proof of this concept but I can't physically understand what's exactly going on. How does the force acting on some random point 'travel' to the COM and cause it to move in a particular well-defined manner?
 A: If you understand the mathematical proof then there is nothing else to worry about. The physical objects and forces do not have any conception of the COM, but it just so happens that we can use our minds to realise that the system will behave as if the forces only work on the COM. It is not true that they 'travel' there or anything, it's just that the maths works out in such a way that if we pretend that's what's happening we will get the right answer. There doesn't need to be anything apart from the maths which tells us we will get the correct answer by pretending that this is how it works. 

As an example we can think about multiplication. We can work out using maths that $a \times b = b \times a$. So if I give you 5 boxes with 3 apples in each box you could 'pretend' I'd given you 3 boxes with 5 apples, and you would still know that I'd given you 15 apples; the apples and boxes don't have to do anything for this to work out. 
A: 
How does the force acting on some random point 'travel' to the COM and
  cause it to move in a particular well-defined manner?

If we are dealing with a rigid body, the applied force indeed "travels" to all points of the body, so that they all of them, including the COM, have the same translational acceleration.
The mechanism of the force distribution is an internal mechanical stress, which could be a combination of tension, compression and shear.
It is easy to see on the diagram below, where a rigid block is accelerating due to the internal tensile stress.
 
For instance, for the rear half of the block to have the same acceleration as the front half, the tension force between the two halves has to be half of the applied force.
In another example, closer to the example in the question, the applied force is distributed through the shear stress. Each small segment of the rod, $m_i$ is accelerated by a force equal to the difference between the forces applied to each side of the segment.
If the mass of the rod is not evenly distributed, the gradient of the stress has to adjust accordingly to support the same translational acceleration for all segments of the rod. 

