What are natural boundary conditions in the calculus of variations? What do people mean, when they speak of natural boundary conditions in the calculus of variations? 

How do natural boundary conditions relate to the Euler-Lagrange equations? 

An example would be fantastic!
Basically two types of boundary conditions are used: Essential or geometric boundary conditions which are imposed on the primary variable like displacements, and Natural or force boundary conditions which are imposed on the secondary variable like forces and tractions. Essential boundary conditions are imposed explicitly on the solution but natural boundary conditions are automatically satisfied after solution of the problem.

Natural Boundary Conditions of the Simplest Kind:
Let $~J : C^2[x_0, x_1] → \mathbb R~$ be a functional of the form of $$J(y) =  \int^{x_1}_{x_0}f(x, y, y') dx$$ and assume that no boundary conditions have been imposed on $~y~$, then $~J~$ have an extremum $~y~$ if the following necessary conditions are satisfied:
$(i)~~$ The ordinate of the extremal satisfies the Euler-Lagrange Equation $$f_y - \frac{d}{dx} f_y' = 0$$
$(ii)~~$ At $~x = x_0~$ $$\left|\frac{\partial f}{\partial y'}\right|_{~x_0}=0$$
$(iii)~~$  At $~x = x_1~$ $$\left|\frac{\partial f}{\partial y'}\right|_{~x_1}=0$$
From the perspective of computational math: Solving a differential equation using e.g. finite elements you usually build a linear equation $Ax = b$ where $x$ is a discrete approximation of the solution. You set up $A$ and $b$ depending on different aspect of your problem, like how your domain looks like and also what kind of boundary conditions there are. 

We speak of natural boundary conditions, if during assembly of the problem, this step of adding the information of boundary conditions is effectivly skipped. It's those boundary conditions that "naturally" arise when we don't pay attention to them.

See also here: Neumann = 0 boundary condition drops the term for boundary conditions completely, so we don't have to worry about them.