How can I see the relation between shtukas and the Langlands conjecture?

I was hoping someone arithmetically qualified would take this on, but here are some comments from a geometer. One nice perspective I learned from Wei Zhang's ICM address - namely, over function fields of curves over finite fields you have moduli spaces of shtukas with arbitrarily many legs (points in the underlying curve where a modification is taking place) -- these come with a map to a Cartesian power of the curve, where we remember only the location of the modification. Over number fields there are only analogs of moduli of shtukas with no legs (the arithmetic locally symmetric spaces which are the home of automorphic forms) and with one leg (Shimura varieties, with the defining map to $Spec(Z)$ being the analog of the "position of leg" map to the curve.

Which is to say, general moduli of shtukas DON'T have an obvious number field analog, rather they are certain generalizations of Shimura varieties (eg moduli of elliptic curves) that make sense over function fields. [Though over local fields there are now analogs of arbitrary moduli of local shtukas.]

Before saying what they ARE exactly, maybe it's worth saying a reason why it's clear they could be useful in the Langlands program. Namely, they carry the same symmetries (Hecke correspondences) as the [function field versions of] arithmetic locally symmetric spaces. As a result, their etale cohomology carries an action of a Hecke algebra, commuting with its natural Galois action. Once you find this out, and you take the point of view that we are looking for a vector space with commuting actions of Galois groups and Hecke algebras in which we might hope to realize the Langlands correspondence, then etale cohomology of moduli of shtukas is a natural place to look, and I imagine this is close to Drinfeld's reasoning (the same picture is one explanation for the role of Shimura varieties).

Anyway to say what they are start with Weil's realization that the function field analog of an arithmetic locally symmetric space is the set of $F_q$ points of the moduli stack of $G$-bundles on a curve:

$$Bun_G(C)(F_q)= G(F)\backslash G(A_F) / G(O_{A_F})$$

where $F$ is the field of rational functions on a smooth projective curve $C$ over a finite field, $A$ and $O_A$ are the adeles and their ring of integers.

So this is just a discrete set, but it comes from a rich geometric object over the algberaic closure of $F_q$. Next you realize that this set is given as fixed points of Frobenius acting on the stack $Bun_G(C)$ over the algebraic closure

$$Bun_G(C)(F_q)= (Bun_G(C))^{Frob}$$

-- i.e. the moduli stack of $G$-bundles equipped with an isomorphism with their Frobenius twist.

Then you say, ok let's relax this condition. Given two $G$-bundles you have the notion of a modification at a point $x\in C$ (or a finite collection of points) -- namely an isomorphism between the two bundles away from these points, with a fixed "relative position" at these points (relative positions measure the pole of this isomorphism at the points it degenerates -- you want to bound or prescribe this pole in a trivialization-independent way). This is the geometric source of [spherical] Hecke correspondences.

So now you can ask for the following data: a G-bundle, together with an isomorphism with its Frobenius twist away from finitely many points (the "legs") and fixed relative positions. These are shtukas! Also note that at points of the curve away from the legs we've "done nothing", from which it follows that the same Hecke correspondences that act on the original automorphic space act on the moduli of shtukas and their cohomology.

From the "modern" point of view (cf Vincent Lafforgue), we shouldn't just fix some minimal collection of "legs" and relative positions at those legs, but consider the entire tower of moduli of shtukas with arbitrary many legs and relative positions, and in particular pay attention to the algebraic structure ("factorization") we get by letting the positions of the legs collide. Lafforgue showed that this structure is enough to see the Langlands correspondence -- or rather one direction, it explains how spaces of automorphic forms "sheafify" over the space of Galois representations. I recommend Gaitsgory's "How to invent shtukas" and Nick Rozenblyum's recent lectures at the MSRI Intro workshop for the Higher Categories program for a very natural explanation of all of this starting from the geometric Langlands POV.

To flesh this out just a tiny bit, geometric Langlands replaces functions on $Bun_G(C)(F_q)$ by the study of the stack $Bun_G(C)$, where again the fundamental object of study is the action of Hecke correspondences (this time acting on categories of sheaves rather than vector spaces of functions). From this starting point you recover the entire story of shtukas very naturally by thinking categorically about the Grothendieck-Lefschetz trace formula for Frobenius acting on $Bun_G(C)$ -- cohomology of shtukas is just what you get when you apply the trace formula to calculate trace of Frobenius composed with a Hecke correspondences. So from this point of view shtukas are not "something new we've introduced", but really a structural part of thinking abstractly on the Hecke symmetries of $Bun_G$.

${\bf Edit:}$ I can't resist adding an "arithmetic field theory" perspective. From the Kapustin-Witten point of view on the Langlands program as electric-magnetic duality in 4d topological field theory, shtukas have the following interpretation.

First of all a curve over a finite field plays the role of a 3-manifold, so a 4d TQFT attaches to it a vector space (here the [functional field version of] the space of automorphic forms).

Second [spherical] Hecke correspondences are given 't Hooft lines, which are codimension 3 defects (AKA line operators) in the field theory. These are labeled by the data that labels relative positions of bundles on a curve (representations of the Langlands dual group).

So you find that the theory has not just one vector space attached to a "3-manifold" like a curve over a finite field, but one attached to each labeling of a configuration of points of the "3-manifold" by these data. (relative positions). This is how cohomology of moduli of shtukas appear (schematically of course!) in the physics POV.

I think shtukas are best understood ahistorically. I would start with the modular curves, but specifically with the (geometric) Eichler-Shimura relation. This says that the Hecke operator at $p$, viewed as a correspondence on $X_0(N) \times X_0(N)$, when reduced at characteristic $p$, is just the graph of Frobenius plus the transpose of the graph of Frobenius. The relevance of this fact to the proof of a Langlands correspondence that relates traces of Frobenius acting on cohomology to eigenvalues of Hecke operators acting on cohomology should be unsurprising, even if completing the argument required much brilliant work by many people.

Now for higher-dimensional Shimura varieties, one cannot always generalize this simple geometric Eichler-Shimura relation, and instead must state and prove a suitable cohomological analogue of it.

When we go to the function field world, on the other hand, it pays to be very naive. We want to define a moduli space of some kind of object where Hecke operators act, and Frobenius acts, and these two actions are related. As David Ben-Zvi described in his answer, we understand what kind of object Hecke operators act on, and how - they act on vector bundles, or more generally $G$-bundles, and they act by modifying the bundle at a particular point in a controlled way. Frobenius also acts on $G$-bundles, by pullback. But these actions have nothing to do with each other.

The solution, then, is to force these actions to have something to do with each other in the simplest possible way - demand that the pullback of a $G$-bundle by Frobenius equal its modification at a particular point, in a certain controlled way. In fact, we can freely do this at more than one point, producing a space on which Frobenius acts like any desired composition of Hecke operators at different points.

The actual way Drinfeld came up with the definition was totally different, and did involve differential operators. He first came up with Drinfeld modules by an inspired analogy with the moduli spaces of elliptic curves. He then realized an analogy with work of Krichever, which he realized should lead to an analogous object defined using sheaves, the resulting definition was a shtuka. Precisely, the relation is that a rank $r$ Drinfeld module is the same thing as a $GL_r$-shtuka with two legs (corresponding to the standard representation of $GL_r$ and its dual under the geometric Satake isomorphism, in the modern language) at two points, where one is allowed to vary and the other is fixed at the point "$\infty$", and furthermore where we require that the induced map of vector bundles at the point $\infty$ is nilpotent.

So moduli spaces of Drinfeld modules will be certain subsets of moduli spaces of shtukas. However, the relationship between Drinfeld modules and shtukas is rarely used to study either - the research on both of them is usually quite separate.