Interpretation of the action in classical mechanics In classical mechanics the dynamics on a manifold $M$ are characterised by the minimisation of a functional
$$ \min_{q \in C^\infty(\mathbb{R},M)} \int_{\mathbb{R}}L(q(t),\dot{q}(t))dt, $$
where $L:TM\to\mathbb{R}$ is a smooth function, the "Lagrange function". In the case of a particle of mass $m$ constrained to a submanifold $M\subseteq \mathbb{R^n}$ moving in a potential $V: M \to \mathbb{R}$ the Lagrangian is given by $L(x,v):=\frac{1}{2}m\|v\|^2 - V(x),$ so the functional to minimise (the "action") is 
$$ C^\infty(\mathbb{R},M)\ni q \mapsto\int_{\mathbb{R}}\left( \frac{1}{2}m\|\dot{q}(t)\|^2 - V(q(t)) \right)dt \in \mathbb{R}.$$
This is all standard in physics and many "derivations" of this  from variants of Newton's second law on $M$ are given in the physics literature. What I've never seen attempted is an explanation of this: What is the intuition behind formulating the dynamics in terms of a variational principle? Are there any heuristics on the interpretation of the action?
It seems that the action is some sort of "currency": Every path in $M$ comes at a cost and nature somehow chooses that path that costs the least amount. But how to interpret this amount? Why should the currency take the form:
$$\text{"kinetic energy} - \text{potential energy"} ?$$
EDIT 1: I'm not looking for a "historical explanation" on how this principle was discovered. I'm more looking for a direct interpretation of the action if this makes sense.
EDIT 2: As pointed out by arsmath the dynamics needn't be characterised by a minimum of the action, it can also happen that merely the derivative of the action vanishes and we have a stationary point (or a maximum!).
 A: While the following may be less “physically” intuitive than the question intends, I liked it when I heard it. If you believe in the importance of Poisson brackets, it is natural to ask if they make the Lie algebra of some transformation group, or in other words, if they can be realized as Lie brackets of vector fields.
This question was answered in the 1960s by “prequantization” of symplectic manifolds, but in the case of $X=\smash{\mathbf R^2}$ with points $x=(p,q)$ and 2-form $\omega=dp\wedge dq$, already by Sophus Lie in (1890, p. 270): one considers $L=X\times\mathbf U(1)$ with points $ξ=(x,z)$, projection $ξ\mapsto x$ and connection (contact) 1-form $\varpi = p\,dq + dz/iz$. Then one checks that an automorphism $g\in\operatorname{Aut}(L,\varpi)$, i.e. a diffeomorphism such that $g^*\varpi = \varpi$, must have the form
$$
g(x,z) = (s(x),ze^{iS(x)})
\tag1
$$
where $s\in\operatorname{Aut}(X,\omega)$ is a symplectomorphism and the function $S$ is determined up to an additive constant1) by
$$
p\,dq-s^*(p\,dq)=dS.
\tag2
$$
Likewise the Lie algebra $\operatorname{aut}(L,\varpi)$ is isomorphic to $(C^∞(X), \{\cdot,\cdot\})$: to any $\varpi$-preserving vector field $Z$ we can attach the function $H(x) = \varpi(Z(ξ))$ called its Hamiltonian, and conversely any $H ∈ C^∞(X)$ gives rise to the infinitesimal automorphism
$$
Z(x,z)= (\operatorname{drag}H(x),iz\ell(x))
\tag3
$$
where $\operatorname{drag}H=\smash{\bigl(-\frac{\partial H}{\partial q},\frac{\partial H}{\partial p}\bigr)}$ is the symplectic gradient, and $\ell= p\frac{\partial H}{\partial p}-H$ is the Lagrangian for you. This is the only “derivation of it from something else” I ever liked. Opinions may vary :-)
Now paths $t\mapsto x$ in $X$ “lift” to paths in $L$ where $z$ spins around the “internal clock” $\mathbf U(1)$ so eloquently described in Feynman’s QED, evolving with $S=\int\ell\,dt$. “Wave functions” live in the complex plane it spans, and constructive interference of the waves corresponds to stationary $S$.
Added: At a more classical level, I can only recommend reading the 18-page Introduction of Souriau (1997, French version) where he explains from first Newtonian (or really D’Alembert) principles, not the Poincaré-Cartan 1-form $p\,dq - H\,dt=(p\dot q-H)dt=\ell\,dt$ but the Lagrange 2-form $dp\wedge dq - dH\wedge dt$ and generalizations which are (he argues) the only intrinsic objects worth talking about at non-quantum level. At (12.98) he explains why he abandoned the variational approach of a previous book — just as Lagrange also did 200 years earlier. Worth pondering?

1) That is to say, one has a central extension $1\longrightarrow\mathbf U(1)\longrightarrow\operatorname{Aut}(L,\varpi)\longrightarrow\operatorname{Aut}(X,\omega)\longrightarrow 1$ which “integrates” $0\longrightarrow\mathbf R\longrightarrow C^∞(X)\overset{\operatorname{drag}}{\longrightarrow}\operatorname{aut}(X,\omega)\longrightarrow 0$.
A: I think it is more transparent to answer your question in the Hamiltonian formulation of mechanics rather than the Lagrangian one. In the nondegenerate case, that is, where the Legendre transform or fibrewise derivative is a diffeomorphism, they coincide anyway. Let $(M,d\alpha)$ be an exact symplectic manifold. For $-\infty < t_0 < t_1 < +\infty$ and $x_0,x_1 \in M$ define $$C^\infty_{x_0,x_1}([t_0,t_1],M) := \{\gamma \in C^\infty([t_0,t_1],M) : \gamma(t_0) = x_0 \text{ and } \gamma(t_1) = x_1\}$$ as well as the Hamiltonian action functional $$\mathcal{A}^H \colon C^\infty_{x_0,x_1}([t_0,t_1],M) \to \mathbb{R}, \qquad \mathcal{A}^H(\gamma) := \int_{\gamma}\alpha - \int_{t_0}^{t_1}H \circ \gamma.$$
Then the critical points of $\mathcal{A}^H$ coincide with the integral curves of the Hamiltonian vector field $X_H$. As was already correctly noted in the comments, we are interested in critical points rather than minima, as they do not necessarily exist. Thus to answer your question:

The Principle of least action is an equivalent way to encode the dynamics of a Lagrangian or Hamiltonian system.

Note that the terminology "principle of least action" is a bit unfortunate. 
A: It's not the case that the action is always minimized in physics -- the result is purely that it's a stationary point of the action.  This has come up several times at Physics Stack Exchange:


*

*When is the principle of stationary action not the principle of least action?

*Is Action Always “Locally” Least?
This raises the question of "Why a stationary point?", which Carlo's answer explains, but the examples above undermine the "currency" implication.
A: In a way, the action is really best understood in a quantum-theoretical context, where it naturally emerges from Feynman's principle: essentially, one evaluates matrix elements of the time evolution operator $U(t',t)={\rm e}^{-i\hat{H}(t'-t)}$ with $\hat{H}=T(\hat{p})+V(\hat{q})$ by applying the Lie-Trotter formula, inserting complete sets of eigenstates of $\hat{q}$ and $\hat{p}$, and integrating over the eigenvalues of $\hat{p}$, which leaves one with a time-discretized path integral containing (a discretization of) $\int L(q,\dot{q})\,{\rm d} t$, and in the limit one obtains the usual Feynman path integral involving the action.
There is a natural connection from this to the principle of least action by considering quantization as the inverse (in some sense) of tropicalization: Consider $M$ as a category with points as objects and paths as morphisms, and consider dynamics as coming from a functor from $M$ into a rig; where quantum theory assigns each path an amplitude $U\in\mathbb{C}$ such that concatenation of paths corresponds to multiplication of amplitudes and multiple paths between the same points interfere via addition, the classical theory assigns each path an action $S\propto\log U\in\mathbb{R}$ such that concatenation of paths corresponds to addition and multiple paths between the same points interfere via taking the minimum. There is a body of work along those lines by John Baez (cf. these lecture notes) and others.
A: One could also mention the Special and General Relativity. The postulate is that the dynamic of a particle is a geodesic. More precisely it minimizes the quantity
$$ A=\int mc\sqrt{ds^2} $$ where $$ ds^2 = (1+\frac{2V}{mc^2})c^2dt^2 - dx^2-dy^2-dz^2 $$
with $V$ is the potential. See for example the Schwarzschild metric ( https://en.wikipedia.org/wiki/Schwarzschild_metric), where the Newton potential appears and we neglected the modifications on the space which are of smaller order for large $c$. Then 
$$ A= \int mc\sqrt{c^2+\frac{2V}{m}-\frac{dx^2}{dt^2}-\frac{dy^2}{dt^2}-\frac{dz^2}{dt^2}}dt $$
and for large $c$ $$A=\int mc^2dt -\int \Big(\frac{1}{2}m(\frac{dx^2}{dt^2}+\frac{dy^2}{dt^2}+\frac{dz^2}{dt^2})-V\Big)dt+\mathcal{O}(\frac{1}{c^2})$$
Therefore, the action can be seen as the first order of the path length. 
EDIT: True we start from a minimising principle (geodesic) to obtain another minimizing principle (with the Lagragian), however the first one is somehow more fundamental than the second one.
A: Even though the historical order is the other way around, it is helpful to start from wave/quantum mechanics and arrive at classical mechanics in the limit that the wave length of the particle goes to zero. Mathematically, that limit is the stationary phase approximation, meaning that classical trajectories are perpendicular to surfaces of constant phase. The phase is the action = integral of Lagrangian $L$, as first realized by Dirac, and as follows immediately by calculating the phase $\phi$ accumulated in a time $T$,
$$\phi=\int_0^T(p\dot{q}-H)\,dt=\int_0^T L(q,\dot{q})\,dt.$$
From this equation you see that the Lagrangian is "kinetic minus potential energy" because it is the difference of $p\dot{q}$ = twice the kinetic energy and the sum of kinetic and potential energy (the Hamiltonian $H$). In this way stationary phase amounts to stationarity of the action.
A: If you're interested in quantum-mechanical motivations/generalizations of results in classical mechanics, we can give one in particular for the given action. The transition probability amplitude between two states over time is proportional to $\exp\frac{i\delta 
 S}{\hbar}$, where $S$ turns out to be the usual action. In particular, the exponent is a definite integral; the interval of time over which we integrate $L$ to give $S$ is the initial-to-final-state time period. We call this $S$ a path integral. Verifying $L=\frac12m\dot{x}^2-V(x)$ is a fairly involved calculation, explored at the linked section. The article as a whole shows the path integral formulation is equivalent to the Schrödinger equation; the $SE\implies PI$ part gives the form of $L$.
In quantum field theory, more general path integrals arise, but they too give rise to Euler-Lagrange equations. The reason is that if each transition has an amplitude $\propto\exp\frac{i\delta S}{\hbar}$, interference between $\delta S\ne0$ states is destructive, which is why we observe $\delta  S=0$ states. (Note this is a motivation for stationary actions, not minimized ones.) This is related to $\int_{\Bbb R}\exp ikxdx=2\pi\delta(k)$.
A: (While this is my first answer here, I have been active on physics.stackexchange for multiple years, specifically in the subject of classical mechanics.)

The action is purely a mathematical instrument.
In the image below the curves represent the case of an object being thrown upwards against a potential that gives a 2 $m/s^2$ acceleration: it rises and descends again. With 2 $m/s^2$ acceleration and duration of 2 seconds the true trajectory reaches a height of 1 meter.
Black curve: trajectory of the object
red curve: kinetic energy
green curve: minus potential energy

When you sweep out a range of trial trajectories the curves of the energies change accordingly.
The image displays the point in variation space where the trial trajectory hits the true trajectory: then the red curve (kinetic energy) and the green curve (minus potential energy) are parallel to each other. (They're parallel of course since the rate at which the kinetic energy is changing must match the rate at which the potential energy is changing.)
So: what you need is a method to know where the slopes of the red/green curves are not equal, and where they are.
To that end we use the following property of the value of an integral: when start point and end point of a curve are fixed then when the slope of that curve changes the value of that curve's integral changes in proportion.
In the image below the curves on the left are the same as the curves of the first image. The curves on the right are the corresponding functionals.

In the example presented here (2 $m/s^2$ acceleration) the potential increases linear with height. The green line on the right shows how the integral of the minus potential energy responds to variation of the trial trajectory. Here the green functional is a straight line because here the potential energy increases linear with height. The red functional represents how the integral of the kinetic energy responds to variation of the trial trajectory. Since the kinetic energy is a quadratic function of the velocity the red functional is a quadratic function of the variational parameter.
There is only one point where the respective values of the two integrals change at the same rate (changing in opposite direction). That point is the point where the trial trajectory hits the true trajectory.
About generality:
The way the integral of the potential energy responds to variation of the trajectory will in general be different from the way the integral of the kinetic energy responds to variation. This is independent of the way the variation is implemented.
Emphasizing a key point:
The purpose of the integration is to obtain information about the slope of the potential/kinetic energy curve of the trial trajectory. Slope information is usually obtained with differentation, but in this case with integration.

This particular example is the simplest case: a potential that increases linear with height. The reasoning generalizes to all cases.

General discussion:
The concept of Hamilton's stationary action has both physics content and mathematical content.
The physics content consists of the Work-Energy theorem.
The rest is mathematical instrument.

[Later edit]
Below is an animated GIF, showing how the curves representing the energies respond to variation of the trial trajectory. The slider changes the variational parameter.


(The images illustrating this answer are my own work, they're screenshots of diagrams from my own website. )
