how to find the varieties whose cohomology realizes certain representations?
Regarding Shimura varieties:
One has to first consider the case of modular curves, which has served throughout as an impetus and inspiration for the general theory.
The study of modular curves (in various guises) goes back to the 19th century, with the work of Jacobi and others on modular equations (which from a modern viewpoint are explicit equations for the modular curves $X_0(N)$). The fact that these curves are defined over $\mathbb Q$ (or even $\mathbb Z$) also goes back (in some form) to the 19th century, in so far as it was noticed that modular equations have rational or integral coefficients. There is also the (strongly related) fact that interesting modular functions/forms have rational or integral $q$-expansion coefficients. Finally, there are the facts related to Kronecker's Jugendtraum, that modular functions/forms with integral Fourier coefficients, when evaluated at quadratic imaginary points in the upper half-plane, give algebraic numbers lying in abelian extensions of quadratic imaginary fields. These all go back to the 19th century in various forms, although complete theories/interpretations/explanations weren't known until well into the 20th century.
The idea that the cohomology of modular curves would be Galois theoretically interesting is more recent. I think that it goes back to Eichler, with Igusa, Ihara, Shimura, Serre, and then Deligne all playing important roles. It seems to be non-trivial to trace the history, in part because the intuitive idea seems to predate the formal introduction of etale cohomology (which is necessary to make the idea completely precise and general). Thus Ihara's work considers zeta-functions of modular curves (or of the Kuga--Satake varieties over them) rather than cohomology. (The zeta-function is a way of incarnating the information carried in cohomology without talking directly about cohomology). Shimura worked just with weight two modular forms (related to cohomology with constant coefficients), and instead of talking directly about etale cohomology worked with the Jacobians of the modular curves. (He explained how the Hecke operators break up the Jacobian into a product of abelian varieties attached to Hecke eigenforms.) [Added: In fact, I should add that Shimura also had an argument, via congruences, which reduced the study of cohomology attached to higher weight forms to the case of weight two forms; this was elaborated on by Ohta. These kinds of arguments were then rediscovered and further developed by Hida, and have since been used by lots of people to relate modular forms of different weights to one another.]
The basic idea, which must have been understood in some form by all these people, is that a given Hecke eigenform $f$ contributes two dimensions to cohomology, represented by the two differential forms $f d\tau$ and $\overline{f}d\tau$. Thus Hecke eigenspaces in cohomology of modular curves are two-dimensional. Since the Hecke operators are defined over $\mathbb Q$, these eigenspaces are preserved by the Galois action on etale cohomology, and so we get two-dimensional Galois reps. attached to modular forms.
As far as I understand, Shimura's introduction of general Shimura varieties grew out of thinking about the theory of modular curves, and in particular, the way in which that theory interacted with the theory of complex multiplication elliptic curves. In particular, he and Taniyama developed the general theory of CM abelian varieties, and it was natural to try to embed that more general theory into a theory of moduli spaces generalizing the modular curves. A particular challenge was to try to give a sense to the idea that the resulting varieties (i.e. Shimura varieties in modern terminology) had canonical models over number fields. This could no longer be done by studying rationality of $q$-expansions (since they could be compact, say, and hence have no cusps around which to form Fourier expansions). Shimura introduced the Shimura reciprocity law, i.e. the description of the Galois action on the special points (the points corresponding to CM abelian varieties) as the basic tool for characterizing and studying rationality questions for Shimura varieties.
In particular, Shimura varieties were introduced prior to the development of the Langlands programme, and for reasons other than the construction of Galois representations. However, once one had these varieties, naturally defined over number fields, and having their origins in the theory of algebraic groups and automorphic forms, it was natural to try to calculate their zeta-functions, or more generally, to calculate the Galois action on their cohomology, and Langlands turned to this problem in the early 1970s. (Incidentally, my understanding is that it was he who introduced the terminology Shimura varieties.) The first question he tried to answer was: how many dimensions does a given Hecke eigenspace contribute to the cohomology. He realized that the answer to this --- at least typically --- was given by Harish-Chandra's theory of (what are now called) discrete series $L$-packets, as is explained in his letters to Lang; the relationship of the resulting Galois representations to the Langlands program is not obvious --- in particular, it is not obvious how the dual group intervenes --- and this (namely, the intervention of the dual group) is the main topic of the letters to Lang. These letters to Lang are just the beginning of the story, of course. (For example, the typical situation does not always occur; there is the phenomenon of endoscopy. And then there is the problem of actually proving that the Galois action on cohomology gives what one expects it to!)
Regarding Drinfeld and Deligne--Lusztig varieties:
I've studied these cases in much less detail, but I think that Drinfeld was inspired by the case of Shimura varieties, and (as Jim Humphreys has noted) Deligne--Lusztig drew insipration from Drinfeld.
What can one conclude:
These theoretically intricate objects grew out of a long and involved history, with multiple motivations driving their creation and the investigations of their properties.
If you want to find a unifying (not necessarily historical) theme, one could also note that Deligne--Lusztig varieties are built out of flag varieties in a certain sense, in fact as locally closed regions of flag varieties, and that Shimura varieties are also built out of (in the sense that they are quotients of) symmetric spaces, which are again open regions in (partial) flag varieties. This suggests a well-known conclusion, namely that the geometry of reductive groups and the various spaces associated to them seems to be very rich.
This is an extended comment, certainly not an answer to the very broad and perhaps unanswerable multiple part question being asked here ("How did people find those varieties?"). A facetious response might be: "With great difficulty and considerable ingenuity." But the question is certainly interesting and might someday inspire a monograph by an expert mathematician deeply interested in the history of late 20th century mathematics. Whether this person will exist is an open question.
Concerning the 1976 Annals paper by Deligne and Lusztig, they provide a certain amount of background discussion in their second section along with a very brief statement: Our work has been inspired by results of Drinfeld, who proved that the discrete series representations of $SL_2(\mathbb{F}_q)$ occur in the cohomology of the affine curve $xy^q - x^q y =1$.
Whereas classical work by Frobenius, Schur, and others, realized the character tables of these groups using orthogonality relations and induction techniques, there was never an explicit realization of the irreducible representations typically of degree $q-1$ (now called the "discrete series" by analogy with the Lie group case). Lusztig made a first investigation of such representations of finite general linear groups in his 1974 Annals of Mathematics Studies paper, motivated in part by the landmark combinatorial 1955 paper by J.A. Green (briefly a Warwick colleague). Ian Macdonald had proposed a general version of the results in that paper for other finite groups of Lie type, which Lusztig made the first serious attack on.
Meanwhile there had been a strong tendency toward translating group actions on (often projective) varieties into linear representations of the groups on (often finite dimensional) cohomology spaces. So a lot of history was coming together by the 1970s to encourage the approach of Deligne and Lusztig. Those wanting to get at least some insight from Lusztig's viewpoint should take a close look at his own comments on his papers including 17, 18, 22: see his MIT webpage here (with a direct link to his updated comments now posted on arXiv).
P.S. David's insightful perspective prompts me to add a few remarks about the fumbling I did in the early 1970s from a completely different direction based on inadequate algebraic methods. (At the time I knew little about Lie group representations and less about modern algebraic geometry.) For finite groups of Lie type, it was already a problem to understand the two large series of (mostly irreducible) characters of $SL_2(\mathbb{F}_q)$, having degrees $q+1, q-1$: "principal" and "discrete" series. The principal series is easily constructed by induction from a Borel subgroup, but the origin of the discrete series is mysterious.
After reduction mod $p$ of these characters (with $q$ a power of $p$), it was obvious that both series exhibited roughly the same behavior. Moreover, this paralleled closely the behavior of the "baby" Verma modules for the Lie algebra of the associated algebraic group (using for powers of $p$ the higher Frobenius kernels). In this example all such modules have dimension $q$, with highest weights of composition factors related by "linkage" under an affine Weyl group relative to $p$. I became convinced in general that what I termed "deformation" of linkage classes made all series of finite group characters look essentially the "same"; by 1980 Jantzen had made this formalism precise. But meanwhile Deligne-Lusztig had found a more profound intrinsic way to understand the finite group characters. For me the main moral is the incredible unity found throughout Lie theory.
The construction of Deligne-Lusztig representations is a very natural analog of the construction of discrete series representations of real groups, and follows a very general philosophy (associated I think with Gelfand and Kazhdan and most probably known to Drinfeld at the time) that all representations of reductive groups over any field are "forms of principal series".
Namely we learn from Harish Chandra and Gelfand--Graev--Piatetskii-Shapiro the idea that representations of a reductive group are "always" labeled by conjugacy classes of tori and characters of the latter (up to Weyl group symmetry). How do we construct these representations? The untwisted case is principal series, ie the case of a split torus. Then we are supposed to perform parabolic induction: look at the big G-representation of functions (or some form of cohomology) on the total space of the natural torus bundle $G/N\to G/B$ over the flag variety and decompose according to the torus action along the fibers (which commutes with G). The theory of (standard/principal series) intertwining operators realizes a Weyl group symmetry on these induced representations.
The philosophy (explained beautifully by Kazhdan in various places, such as his ICM address) is that all other "series" are given as "forms" of the principal series -- ie over the algebraic closure one only has principal series. Put more poetically, the dual of G should have an algebraic structure, so that representations over various fields can be simply specified by descent data from representations over field extensions, so at the end of the day they come from principal series. Over your given field you prescribe a conjugacy class of tori by descent data, which is a conjugacy class of Weyl group representations of your Galois group. So eg over R we just need a conjugacy class of involutions in the Weyl group, over a finite field we can take any conjugacy class in the Weyl group, etc. Now the idea (not yet fully realized in its optimal strength) is that we should twist principal series over the algebraic closure using the "Weyl group action by intertwiners" to define the desired series of representations over the given field.
In any case this idea has a very concrete geometric realization. Recall principal series are functions or cohomologies of a torus bundle over the flag variety. Now given a field k (for simplicity assume the Galois group is cyclic, eg real or finite fields) we can decompose the flag variety over the algebraic closure of k into a collection of G(k) invariant subsets, by looking at flags which are in a given relative position (an element of $W$) with their Galois translates. In the case of $SL_2(R)$ this gives us the decomposition of $CP^1$ into $RP^1$ and the upper+lower half planes. In the finite field case these are Deligne-Lusztig varieties. This is a twisted k-version of G/B, and has a natural version of G/N over it, which is a torsor for precisely the k-torus we specified before by the same Weyl group element. So we can look at functions/cohomologies twisted by characters of this torus, finding a series of representations just as predicted by Harish Chandra. The principal series corresponds to the flag variety over k. For $SL2R$ (an example of a real group with compact torus) we recover the discrete series (though note the representation constructed this way is not irreducible, since we're considering upper and lower half planes together).