I apologize for in advance for making just a few superificial remarks. These are:
The question is not uninteresting. Just because Sha doesn't appear in the definition of L easily, there's no reason one shouldn't ask about manifestations more fundamental than the usual one.
An approach might be to think about the p-adic L-function rather than the complex one. I'm far from an expert on this subject, but the algebraic L-function is supposed to be a characteristic element of a dual Selmer group over some large extension of the ground field. The Selmer group (over the ground field) of course does break up into cosets indexed by Sha. Perhaps one could examine carefully the papers of Rubin, where various versions of the Iwasawa main conjectures are proved for CM elliptic curves.]
Added, 8 July:
This old question came back to me today and I realized that I had forgotten to make one rather obvious remark. However, I still won't answer the original question.
You see, instead of the $L$-function of an elliptic curve $E$, we can consider the zeta function $\zeta({\bf E},s)$ of a regular minimal model ${\bf E}$ of $E$, which, in any case, is the better analogue of the Dedekind zeta function. One definition of this zeta function is given the product
$$\zeta({\bf E},s)=\prod_{x\in {\bf E}_0} (1-N(x)^{-s})^{-1},$$
where ${\bf E}_0$ denotes the set of closed points of ${\bf E}$ and $N(x)$ counts the number of elements in the residue field at $x$. It is not hard to check the expression
$$\zeta({\bf E},s)=L(E,s)/\zeta(s)\zeta(s-1)$$
in terms of the usual $L$-function and the Riemann zeta function.
The product expansion, which converges on a half-plane, can also be written as a Dirichlet series
$$\zeta({\bf E},s)=\sum_{D}N(D)^{-s},$$
where $D$ now runs over the effective zero cycles on ${\bf E}$. This way, you see the decomposition
$$ \zeta({\bf E},s)=\sum_{c\in CH_0({\bf E})}\zeta_c({\bf E},s), $$
in a manner entirely analogous to the Dedekind zeta. Here, $CH_0({\bf E})$ denotes the rational equivalence classes of zero cycles, and we now have the partial zetas
$$\zeta_c({\bf E},s)=\sum_{D\in c}N(D)^{-s}.$$
It is a fact that $CH_0({\bf E})$ is finite. I forget alas to whom this is due, although the extension to arbitrary schemes of finite type over $\mathbb{Z}$ can be found in the papers of Kato and Saito.
It's not entirely unreasonable to ask at this point if the group $CH_0({\bf E})$ is related to $Sha (E)$. At least, this formulation seems to give the original question some additional structure.
Added, 31, July, 2010:
This question came back yet again when I realized two errors, which I'll correct explicitly since such things can be really confusing to students. The expression for the zeta function in terms of $L$-functions above should be inverted:
$$\zeta({\bf E},s)=\zeta(s)\zeta(s-1)/L(E,s).$$
The second error is slightly more subtle and likely to cause even more confusion if left uncorrected. For this precise equality, ${\bf E}$ needs to be the Weierstrass minimal model, rather than the regular minimal model. I hope I've got it right now.
Hi Anweshi,
Since Emerton answered your third grey-boxed question very nicely, let me try at the first two. Suppose $L(s,f)$ is one of the L-functions that you listed (including the first two, which we might as well call L-functions too). (For simplicity we always normalize so the functional equation is induced by $s\to 1-s$.) This guy has an expansion $L(s,f)=\sum_{n}a_f(n)n^{-s}$ as a Dirichlet series, and the most general prime number theorem reads
$\sum_{p\leq X}a_f(p)=r_f \mathrm{Li}(x)+O(x \exp(-(\log{x})^{\frac{1}{2}-\varepsilon})$.
Here $\mathrm{Li}(x)$ is the logarithmic integral, $r_f$ is the order of the pole of $L(s,f)$ at the point $s=1$, and the implied constant depends on $f$ and $\varepsilon$.
Let's unwind this for your examples.
1) The Riemann zeta function has a simple pole at $s=1$ and $a_f(p)=1$ for all $p$, so this is the classical prime number theorem.
2) The Dedekind zeta function (say of a degree d extension $K/\mathbb{Q}$) is a little different. It also has a simple pole at $s=1$, but the coefficients are determined by the rule: $a(p)=d$ if $p$ splits completely in $\mathcal{O}_K$, and $a(p)=0$ otherwise. Hence the prime number theorem in this case reads
$|p\leq X \; \mathrm{with}\;p\;\mathrm{totally\;split\;in}\;\mathcal{O}_K|=d^{-1}\mathrm{Li}(x)+O(x \exp(-(\log{x})^{\frac{1}{2}-\varepsilon})$.
This already has very interesting applications: the fact that the proportion of primes splitting totally is $1/d$ was very important in the first proofs of the main general results of class field theory.
3) If $\rho:\mathcal{G}_{\mathbb{Q}}\to \mathrm{GL}_n(\mathbb{C})$ is an Artin representation then $a(p)=\mathrm{tr}\rho(\mathrm{Fr}_p)$. If $\rho$ does not contain the trivial representation, then $L(s,\rho)$ has no pole in neighborhood of the line $\mathrm{Re}(s)\geq 1$, so we get
$\sum_{p\leq X}\mathrm{tr}\rho(\mathrm{Fr}_p)=O(x \exp(-(\log{x})^{\frac{1}{2}-\varepsilon})$.
The absence of a pole is not a problem: it just means there's no main term! In this particular case, you could interpret the above equation as saying that "$\mathrm{tr}\rho(\mathrm{Fr}_p)$ has mean value zero.
4) For an elliptic curve, the same phenomenon occurs. Here again there is no pole, and $a(p)=\frac{p+1-|E(\mathbb{F}_p)|}{\sqrt{p}}$. By a theorem of Hasse these numbers satisfy $|a(p)|\leq 2$, so you could think of them as the (scaled) deviation of $|E(\mathbb{F}_p)|$ from its
"expected value" of $p+1$. In this case the prime number theorem reads
$\sum_{p\leq X}a(p)=O(x \exp(-(\log{x})^{\frac{1}{2}-\varepsilon})$
so you could say that "the average deviation of $|E(\mathbb{F}_p)|$ from $p+1$ is zero."
Now, how do you prove generalizations of the prime number theorem? There are two main steps in this, one of which is easily lifted from the case of the Riemann zeta function.
Prove that the prime number theorem for $L(s,f)$ is a consequence of the nonvanishing of $L(s,f)$ in a region of the form $s=\sigma+it,\;\sigma \geq 1-\psi(t)$ with $\psi(t)$ positive and tending to zero as $t\to \infty$. So this is some region which is a very slight widening of $\mathrm{Re}(s)>1$. The proof of this step is essentially contour integration and goes exactly as in the case of the $\zeta$-function.
Actually produce a zero-free region of the type I just described. The key to this is the existence of an auxiliary L-function (or product thereof) which has positive coefficients in its Dirichlet series. In the case of the Riemann zeta function, Hadamard worked with the auxiliary function $ A(s)=\zeta(s)^3\zeta(s+it)^2 \zeta(s-it)^2 \zeta(s+2it) \zeta(s-2it)$. Note the pole of order $3$ at $s=1$; on the other hand, if $\zeta(\sigma+it)$ vanished then $A(s)$ would vanish at $s=\sigma$ to order $4$. The inequality $3<4$ of order-of-polarity/nearby-order-of-vanishing leads via some analysis to the absence of any zero in the range $s=\sigma+it,\;\sigma \geq 1-\frac{c}{\log(|t|+3)}.$ In the general case the construction of the relevant auxiliary functions is more complicated. For the case of an Artin representation, for example, you can take $B(s)=\zeta(s)^3 L(s+it,\rho)^2 L(s-it,\widetilde{\rho})^2 L(s,\rho \otimes \widetilde {\rho})^2 L(s+2it,\rho \times \rho) L(s-2it,\widetilde{\rho} \times \widetilde{\rho})$. The general key is the Rankin-Selberg L-functions, or more complicated L-functions whose analytic properties can be controlled by known instances of Langlands functoriality.
If you'd like to see everything I just said carried out elegantly and in crystalline detail, I can do no better than to recommend Chapter 5 of Iwaniec and Kowalski's book "Analytic Number Theory."
Best Answer
Regarding the first of these conjectures, I believe it was first explicitly stated (in the more general setting of a relative extension $K/k$) in Artin's 1923 paper [Über die Zetafunktionen gewisser algebraischer Zahlkörper, Math. Ann. 89, pp. 147-156]. This of course is a very special case of the general Artin holomorphy conjecture, and it is easy in the case of a normal extension. Dedekind did the case of pure cubic fields, but doesn't this result of his date to much later than 1873? Artin quotes the following paper from 1900, and attributes to it the result on pure cubic fields: [Dedekind, Über die Anzahl von Idealklassen in reinen kubischen Zahlkörpern, the Crelle journal, vol. 121, pp. 40-123].