Diagrams as abbreviations
Let's ignore physics for a moment. A Feynman diagram is a graphic abbreviation for a quantity like
$$
\omega(x,y,z) = \int du\,dv\,dw\ A(x-u)B(y-v)C(z-w)D(u-v)E(v-w)F(w-u).
\tag{1}
$$
Lowercase letters represent points in spacetime. Each uppercase letter in the integrand is a function depending on the difference between two points. Some points ($x$, $y$, and $z$ in this example) occur in only one factor, and we don't integrate over them. Other points ($u$, $v$, and $w$ in this example) occur in more than one factor, and we do integrate over them. This particular example is represented by a Feynman diagram that looks like this:
Each factor in the integrand is represented by a line. Each variable is represented by a point, so if two factors share the same variable, their lines are connected to each other. More generally, as mentioned in the question, the factors $A,B,C,D,E,F$ in the integrand may also involve indices that may be contracted with each other in various ways, but this simple example illustrates the idea.
How Feynman diagrams arise in physics
In physics, quantities of the form (1) — Feynman diagrams — arise from using perturbation theory as a computational method in field theory. Perturbation theory is typically used when the equations of motion for the fields are nonlinear, which makes exact solutions unattainable, and when the nonlinearities (also called interactions) are weak. Then, by expanding everything in powers of the coefficient(s) of the nonlinear terms, we can sometimes get a good approximation to the exact solution. Perturbation theory is the art of doing that kind of expansion.
By the way, this is not specific to quantum field theory. Feynman diagrams are just as appropriate in classical field theory. One difference is that in classical field theory, Feynman diagrams don't have loops. Loops, like the triangular loop in the diagram shown above, are a special feature of quantum field theory. In this answer, I'll focus on quantum field theory, where the diagrams can be interpreted in terms of particles... well, sort of. More about this below.
Integrals like (1) arise when we start with a correlation function in the full nonlinear model and expand it in powers of the interaction strength — that's perturbation theory. Each diagram represents a term in this expansion. Each such term is a combination of quantities that we can calculate exactly in the linear (non-interacting) version of the model. In the example above, each of the factors $A,B,C,D,E,F$ represents a two-point correlation function in the linear version of the model. The things being correlated are field operators.
The question is, how is any of this related to particles?
Feynman diagrams and particles
In a quantum field theory with linear equations of motion, the field operators are typically directly realted to particles. Applying a field operator to the vacuum state typically gives a single-particle state. As a result, the vacuum correlation function of a product of two field operators can be interpreted as an inner product between two single-particle states. We can think of such an inner product as the amplitude (whose magnitude-squared is the probability) for a particle that is initially here to be detected there, where "here" and "there" may be separated in time and/or space. That's why we call the correlation function a propagator.
In a quantum field theory with nonlinear equations of motion, field operators typically do not correspond to particles in such a simple way. Applying a field operator to the vacuum state does not create a purely single-particle state, so an exact two-point correlation function (propagator) generally does not represent the propagation of a single particle. However, with some technical caveats, the state created by a field operator may include a single-particle term (as part of a quantum superposition with other terms), and we can extract the desired single-particle contribution to the propagator by applying an appropriate differential operator to it. This is the idea behind the LSZ reduction formula highlighted in the answer by user1379857. The LSZ reduction formula relates an exact $N$-point correlation function to a scattering amplitude for $N$ particles in the nonlinear theory.
Calculating correlation functions exactly is usually beyond our reach, though, so we resort to perturbation theory: we expand everything in powers of the interaction strength, the coefficient of the nonlinear terms in the equations of motion. Each term in this expansion has the form illustrated in equation (1), where $A,B,C,D,E,F$ are two-point correlation functions in the linear model, with the interaction strength set to zero. In the linear model, those lines would correspond to particles in the way described above. But the linear model is only being used here as an artificial device to calculate something in the nonlinear model. In the nonlinear model, interpreting those lines as particles is usually not valid. Experts often still refer to them as "particles" because it's easy, entertaining, or whatever. Sometimes they'll use the adjective "virtual" as a warning, but it's still just jargon.
However, there are situations in which the exact scattering amplitude in the nonlinear theory is dominated by one term in the expansion, and some of those situations really do involve a physically observable intermediate particle phenomenon that really does correspond fairly directly to an internal line in the dominant Feynman diagram! Furthermore, the distinction between those situations and more typical situations is fuzzy. That's why this answer is... fuzzy.
To really understand the relationship between Feynman diagrams and particles, I recommend working toward a nonperturbative understanding of particles in quantum field theory. Exact nonperturbative calculations are usually beyond reach, but we can still use nonperturbative principles as the foundation for how we think about quantum field theory. Perturbation theory is a tool in the toolbox. It's not the thing we're trying to build.
