As I understand it (If I'm imprecise, as I will likely be, please correct me), Langlands says roughly as follows:

For every representation $Gal(\mathbb{Q}) \rightarrow GL_n(\mathbb{C})$ we can form a function, called the associated $L$-function.

There is such a thing called an automorphic form, which in the $n=2$ case is just a modular form (is this right? I have a feeling that there's a subtlety missing here, but I will continue, as this is not yet the gist of my question). For each automorphic form we may associate a function, confusingly also called the associated $L$-function (except now it's associated to an automorphic form rather than a Galois representation).

Langlands says that we get the same set of functions from both of these constructions. (although, as I understand it, it doesn't really say much about what this bijection is)

However, Taniyama-Shimura is phrased in terms of elliptic curves! I'm trying to relate it to something I would recognize as being my rough sketch for Langlands in $n=2$ case.

It is true if an elliptic curve is defined over $\mathbb{Q}$ then one would get a representation of $Gal(\mathbb{Q})$ by its action on the vector space $H^1(E,\mathbb{Q}_l)$ (in the etale sense, for various prime $l$). But this is confusing to me: are all $2$-dimensional representations of this form? And what about this weird varying $l$ (shouldn't the representations ultimately be over $\mathbb{C}$ as in my statement of Langlands, or was that wrong?)?

And how does any of this relate to the phrasing of Taniyama-Shimura that says that any elliptic curve over $\mathbb{Q}$ has a rational map into it from some $X_0(N)$ with integer coefficients?

I hope you can help my confusion...

Edit:
Let me focus my question: in what sense does an elliptic curve give a 2-dimensional representation? (do you look at the first etale cohomology with coefficients in $\mathbb{Q}_l$ and then basechange to $\mathbb{C}$ and it turns out to be indep. of both $l$ and the embedding into $\mathbb{C}$?)

And secondly, do all two dimension (do I need the word "irreducible" here?) representations of the Galois group of the rationals arise from an elliptic curve in this way?

Here are some answers to your various questions:

For the group $GL_2$, every cuspidal automorphic representation of $GL_2(\mathbb A)$ (here $\mathbb A$ is the adele ring of $\mathbb Q$) is generated by a uniquely determined newform, which (when normalized in a suitable fashion) is either a classical newform in the sense of Atkin and Lehner, i.e. a holomorphic cuspform of some weight $k \geq 1$ which is an eigenform for all the Hecke operators, and of minimal possible level for its associated system of Hecke eigenvalues, or else is a Maass newform (same as before but replace holomorphic cuspform of weight $k \geq 1$ by Maass form, which is an eigenform for the Laplacian with some eigenvalue $\lambda$).  

There is a conjecture of Selberg that in the Maass form case, $\lambda \geq 1/4$.  This is still open (although there are known lower bounds that are close); it is an analogue "at infinity" of the Ramanujan--Petersson conjecture.  (More precisely, Langlands explained how to unify Selberg's conjecture with the Ramanujan--Petersson conjecture using the language of automorphic representations and the concept of "tempered" local factors. The local factor at infinity for a holomorphic newform is discrete series (or limit of discrete series in the weight one case), hence automatically tempered, but for Maass forms the local factor at infinity is unitary principal series, and then temperedness is a non-trivial additional condition.) 

It has been proved (essentially by Eichler--Shimura when $k = 2$, by Deligne for the general case of $k \geq 2$, and by Deligne and Serre when $k = 1$) that holomorphic newforms give rise to two-dimensional Galois representations, and it is conjectured (but not proved in general) that $\lambda = 1/4$ Maass forms also give rise to two-dimensional Galois representations.  The Maass forms with $\lambda \neq 1/4$ (i.e. $\lambda > 1/4$ if Selberg's conjecture is true) are not expected to correspond to Galois representations.

What does "give rise to two-dimensional Galois representations" mean exactly? Let me explain.  (Note: from now on, to avoid circumlocutions, I will write affirmative statements, but in the Maass form $\lambda = 1/4$ case, these remain conjectural in general; in the holomorphic case they are all proved theorems.)

Actually what will happen is that the newform will correspond to a two-dimensional motive.  This motive has $\ell$-adic cohomology, for each $\ell$, and these will form a compatible system of two-dimensional $\ell$-adic representations of $G_{\mathbb Q}$.  

This motive also has a Hodge structure, which has Hodge numbers $(0,0), (0,0)$ in the $\lambda = 1/4$ case, and $(k-1,0), (0,k-1)$ in the holomorphic case.
In the $\lambda = 1/4$ case, or in the holomorphic weight $1$ case, since the Hodge numbers are $(0,0), (0,0)$, the motive will come from a zero-dimensional variety, which is to say it will be a two-dimensional Artin motive, and so the
$\ell$-adic Galois representations can be consolidated into a single Artin
representation $G_{\mathbb Q} \to GL_2(\mathbb C)$.  However, in the holomorphic case when $k \geq 2$, the motive will come from a positive-dimensional variety, and so the $\ell$-adic representations will not be able to be simplified into a single Artin representation (e.g. because they will have infinite image, not finite image).

E.g. in the case $k = 2$, the Hodge numbers are $(1,0), (0,1)$, which says that the motive comes from a certain abelian variety.  The $\ell$-adic representations are then the $\ell$-adic Tate modules (or rather, their duals, if you want to be careful about the distinction betweeh cohomology and homology) of this abelian variety.

I now should say something about coefficients.  The Hecke eigenvalues of the newform will be algebraic numbers, and collectively they will generate a finite extension $E$ of $\mathbb Q$.  The motive attached to the newform will have $E$ acting as endomorphisms, and when I say it it two-dimensional, I mean it is two-dimensional over $E$.  Thus the $\ell$-adic representations will actually be two
dimensional $\lambda$-adic representations for each prime $\lambda$ of $E$, i.e. they will be representations $G_{\mathbb Q} \to GL_2(E_{\lambda})$.

E.g. if $k = 2$ and the newform $f$ has level $N$, then we can form the Jacobian
$J_1(N)$ of $X_1(N)$, and this has an action of $\mathbb T$, the Hecke algebra at level $N$.  The action of $\mathbb T$ on $f$ gives rise to a homomorphism
$\mathbb T \to E$ (sending $T_p$ to the $p$th Hecke eigenvalue of $f$), and
we may form $A_f:= E\otimes_{\mathbb T} J_1(N)$, which is an abelian variety well-defined up to isogeny.  It has dimension $[E:\mathbb Q]$ and endomorphisms by $E$, and so for each $\lambda$ we form its $\lambda$-adic Tate module,
and (the dual of) this is two-dimensional over $E_{\lambda}$, and is the $\lambda$-adic Galois representation attached to $f$.

In particular, if $k = 2$ and $E = \mathbb Q$ (i.e. all the Hecke eigenvalues of $f$ are rational numbers) then $A_f$ is an elliptic curve, and this is the association of elliptic curves to weight two newforms with rational Hecke eigenvalues.  (Note that in this case $f$ automatically has level $\Gamma_0(N)$ rather than $\Gamma_1(N)$, and so in the above we replace $X_1(N)$ and $J_1(N)$ by $X_0(N)$ and $J_0(N)$, which may be a little more familiar.)

Now suppose conversely that $M$ is a motive with endomorphisms by a number field $E$, irreducible and of dimension two over $E$.  It is conjectured that $M$ is attached to a newform.  In fact, we can determine the newform precisely (assuming it exists):
the ramification of $M$ will determine the level, and counting points on $M$ mod primes will determine the Hecke eigenvalues of the newform.   The Hodge numbers of $M$ (possibly after a Tate twist) will be $(i,0),(0,i)$ for some $i \geq 0$.
If $i > 0$, then the newform will have to be a weight $i + 1$ holomorphic newform.  If $i = 0$, then the newform will be either holomorphic weight one,
or a $\lambda = 1/4$ Maass form; to tell which, you have to look at the action of complex conjugation on the Hodge strucuture: if it is non-scalar (this is usually called "odd"), you are in the holomorphic case, while if it is scalar
(this is usually called "even") you are in the Maass case.  (The reason for "odd" and "even" is that in these case the determinant of complex conjugation on the $\ell$-adic cohomology is $-1$ resp. $+1$.)

Let's suppose that the motive $M$ comes from an elliptic curve $C$.  (I use $C$ rather than $E$ because $E$ was my notation for the field of coefficients.)

Then the Hodge numbers are $(1,0),(0,1)$, hence we expect there to be weight two newform $f$ such that $C = A_f$.  (Since $A_f$ is only defined up to isogeny, this equality should be understood as an isogeny.)  But if $C$ is isogenous to a factor of the Jacobian of $X_0(N)$ (which is what we are saying), then this implies (indeed is equivalent to) $C$ being a quotient of $X_0(N)$.

Sometimes things are phrased in terms of $L$-functions rather than motives (because motives are subtle to think about, and parts of the theory of motives remain conjectural).  In the elliptic curve case, though, everything is known, because Faltings proved the Tate conjecture, namely that two elliptic curves with the same $L$-function are isogenous.  Since you can read off the $L$-function from the $\ell$-adic Tate module, this says that even knowing that the $\ell$-adic Tate module of $C$ coincides with the $\ell$-adic Galois representation attached to $f$ (even for a single $\ell$) is enough to get
$C = A_f$.  (This is is why things are sometimes formulated in terms of $L$-functions, sometimes in terms of Galois reps., and sometimes in terms of motives --- the formulations are conjecturally all equivalent, and are known to be equivalent in the elliptic curve case.)

The preceding discussion shows that the general conjecture about going from two-dimensional motives to newforms is a generalization of Shimura--Taniyama.  It is known in the odd case (it follows from Serre's conjecture, proved by Khare, Wintenberger, and Kisin; see Cor. 0.5 of Kisin's paper).  It is open in general in the even case (just as the construction of motives, or Galois representations, from $\lambda = 1/4$ Maass forms is wide open).  (But note that it is proved in the case of solvable image, by Langlands--Tunnel --- see below.)



As I already noted: one can avoid talking about motives, and instead talk about compatible families of $\ell$-adic Galois reps. (more precisely, $\lambda$-adic Galois reps., if we fix our coefficient field $E$), or even $\ell$-adic (or $\lambda$-adic) reps. for a single choice of $\ell$ or $\lambda$. 

There are arrows

$$\text{motives } \to \text{ compatible families of $\ell$-adic reps. } \to \text{ $\ell$-adic rep. for a fixed $\ell$} $$

given by passing to $\ell$-adic cohomology for all $\ell$, and then by picking out a particular $\ell$.  These maps are injective (the first conjecturally in general --- this is the Tate conjecture), but not surjective.  Not all compatible families come from a motive, and not every individual $\ell$-adic rep. sits in a compatible family.  

There is a conjecture of Fontaine and Mazur which (conjecturally!) describes those $\ell$-adic reps. which come from motives. (Here $\ell$ is a fixed prime, and I could just as well be talking about $\lambda$-adic reps. here, but it is more traditional to say $\ell$-adic rather than $\lambda$-adic, even when the latter is what is meant.) In the two-dimensional case, for representations which are supposed to come from holomorphic newforms of weight $k \geq 2$, it is largely proved: see e.g. Thm. 1.2.4 (2), and also the discussion in Section 1.4, of this paper, as well as this paper of Kisin, and these papers
of Calegari.  (These papers all build on the work of Wiles and Taylor--Wiles.)

In the case of representations which are supposed to come from either weight one holomorphic forms or Maass forms with $\lambda = 1/4$, the situation is more complicated.  If you assume that the Galois rep. is odd and has finite image, then it is known to come from a weight one form; this follows from Serre's conjecture, as noted above.  However, it is supposed to be enough (according to Fontaine and Mazur) to assume that the $\ell$-adic representation has finite image on inertia at $\ell$ --- this should then imply that the whole image is finite.  However, this is not proved in general; I believe this result of Buzzard, which handles certain odd cases, is the best general result currently.

In the even case, if you assume that the image is finite and solvable, then Langlands--Tunnel give a $\lambda = 1/4$ Maass form giving rise to your Galois rep., but (still in the even case now), if the image is finite but non-solvable, or (even worse) if you just assume that the image of inertia at $\ell$ is finite, then the conjecture is wide-open.



Note that $2$-dimensional Artin (i.e. finite image) reps. are just a special case of all two-dimensional $\ell$-adic reps. (corresponding to $\lambda = 1/4$ Maass form or weight one forms --- at least conjecturally, in the even case), and the $\ell$-adic Tate modules of elliptic curves are just another special case of such reps.  Even if you write down all the $\ell$-adic reps. coming from all newforms, there are uncountably manner other irreducible two-dimensional $\ell$-adic reps. that don't come from motives at all.
