Outer automorphisms of simple Lie Algebras
Proposition D.40 of Fulton and Harris' Representation Theory states Emerton's comment: the group of outer automorphisms of a simple Lie algebra are precisely the group of graph automorphisms of the associated Dynkin diagram. There is also some discussion of this in Section 16.5 of Humphrey's Introduction to Lie Algebras and Representation Theory.
So for $A_n$ and $n>1$, there is an order 2 automorphism which for $sl_{n+1}$ amounts to negative transpose.
Type B and C have no outer automorphisms.
For $D_n$, there is an order two automorphism swapping the two endpoints, and this corresponds to interchanging the two spin representations. On $so_{2n}$ this is obtained (modulo the inner automorphisms) by conjugating by an orthogonal matrix in $O(2n)$ which has determinant $-1$. For $n=4$, there is also an order 3 automorphism. This is triality, and is discussed in Section 20.3 of Fulton and Harris.
For $E_6$, there is an order 2 automorphism, though I don't know enough about the exceptional Lie algebras to say anything useful about it. But you can find a discussion of the automorphism group in Section 7 of Jacobson's Exceptional Lie Algebras where it is described using Jordan algebras.
For the other 4 exceptional Lie algebras there are no outer automorphisms.
I don't have a good reference, but I can work out the beginning of the answer for you. I will work just over $\mathbb C$, and I will call my simple Lie algebra $\mathfrak g$.
First, you must decide what you mean by "outer automorphism". We know what an automorphism is, and an "inner automorphism" should be conjugation by something. Of course, for $x\in \mathfrak g$, the bracket $\text{ad}_x = [x,-] \in \mathfrak{gl}(\mathfrak g)$ is a derivation of $\mathfrak g$, not an automorphism. So I assume you mean the automorphism $\exp(\text{ad}_x) \in {\rm GL}(\mathfrak g)$ as the inner automorphism. Now, the set of matrices of the form $\exp(\text{ad}_x)$ is not a group, but generates a connected group, which I will call $\text{Inn}(\mathfrak g)$. (Remark: any automorphism of $\mathfrak g$ preserves the Killing form, so we really have $\text\{Inn\}(\mathfrak g) \subseteq \text{Aut}(\mathfrak g) \subseteq \{\rm SO\}(\mathfrak g)$.) Of course, $\mathfrak g$ acts on itself faithfully since it is simple, so $\text{Lie}\bigl(\text{Inn}(\mathfrak g)\bigr) = \mathfrak g$, but $\text{Inn}(\mathfrak g)$ may not be simply-connected. Regardless, it is a quotient of the connected simply-connected simple group $G$ with Lie algebra $\mathfrak g$, and so you could if you prefer consider inner automorphisms to be given by the adjoint action of $G$.
Now, over $\mathbb C$ (and this requires facts about the topology of $\mathbb C$), any two choices of Cartan subalgebra are conjugate by an element of $\text{Inn}(\mathfrak g)$. See, for example, Proposition 5.32 of my notes on the class by M. Haiman. So, to understand $\text{Out}(\mathfrak g) = \text{Aut}(\mathfrak g) / \text{Inn}(\mathfrak g)$, it suffices to understand how it acts any chosen Cartan subalgebra $\mathfrak h$.
Any automorphism of $\mathfrak g$ that fixes $\mathfrak h$ must act on the root lattice, and must take some system of positive roots to some system of positive roots. Now, any two systems of positive roots are related by the Weyl group $W \subseteq {\rm GL}(\mathfrak h^\*)$. (Proposition 5.60 from my notes.) On the other hand, we have $W = \mathcal N_G(H)/H$, the normalizer of the maximal torus $H = \exp \mathfrak h$ in $G$ modulo $H$, which acts trivially on $\mathfrak h$. So $W$ acts on $\mathfrak h$ by inner automorphisms, indeed by $\mathcal N_G(H) \subseteq G$.
A system of positive roots picks out a Cartan matrix and corresponding Dynkin diagram, and conversely from this matrix you can reconstruct the group. Thus, the only possible source of outer automorphisms of come from automorphisms of the Dynkin diagram.
So your question follows simply from looking at the Dynkin diagrams. In particular, $A_1$, the $B$ and $C$ series, and the exceptional groups $G_2,F_4,E_7,E_8$ have no outer automorphisms. For the others, you have to do a calculation. Maybe it's obvious, but it's late; I'll think about it. As others pointed out in the time I took to write this answer, the theorem is that automorphisms of the Dynkin diagram are all outer. Actually, perhaps this is obvious. If an automorphism of the Dynkin diagram were inner, then it would induce among other things an automorphism of $H$, and so be in the Weyl group, and you must convince yourself that non-trivial elements of the Weyl group do not preserve the system of positive roots. But this is essentially the statements that $W$ acts faithfully on $H$ and that each $W$-orbit intersects the positive Weyl chamber only once. So I am using the fact that $W = \mathcal N_G(H)/H$, which off the top of my head right now I don't know how to prove.
Notice that for semisimples, the Dynkin might be disconnected, and clearly any inner automorphism preserves the connected components. So there are certainly outer automorphism for $\mathfrak g^{\times n}$ given by the $S_n$ that permutes the pieces.
Aut(\g) is the semidirect product of Inn(\g) and Out(\g) in the complex AND in the real case. However, this is a rather recent result: tinyurl.com/68748hn
Edit by jc: The link goes to a PDF abstract of:
Hasan Gündogan, The Component Group of the Automorphism Group of a Simple Lie Algebra and the Splitting of the Corresponding Short Exact Sequence, Journal of Lie Theory 20 (2010), No. 4, 709--737.
Abstract: Let $\frak g$ be a simple Lie algebra of finite dimension over $\mathbb K \in \{\mathbb R,\mathbb C\}$ and $\mathop{\rm Aut}(\frak g)$ the finite-dimensional Lie group of its automorphisms. We will calculate the component group $\pi_0(\mathop{\rm Aut}(\frak g)) = \mathop{\rm Aut}(\frak g)/\mathop{\rm Aut}(\frak g)_0$ and the number of its conjugacy classes, and we will show that the corresponding short exact sequence $$ {\bf1}\to\mathop{\rm Aut}(\frak g)_0\to\mathop{\rm Aut}(\frak g)\to\pi_0(\mathop{\rm Aut}(\frak g))\to{\bf1} $$ is split or, equivalently, there is an isomorphism $\mathop{\rm Aut}(\frak g)\cong \mathop{\rm Aut}(\frak g)_0 \rtimes\pi_0(\mathop{\rm Aut}(\frak g))$. Indeed, since $\mathop{\rm Aut}(\frak g)_0$ is open in $\mathop{\rm Aut}(\frak g)$, the quotient group $\pi_0(\mathop{\rm Aut}(\frak g))$ is discrete. Hence a section $\pi_0(\mathop{\rm Aut}(\frak g))\to\mathop{\rm Aut}(\frak g)$ is automatically continuous, giving rise to an isomorphism of Lie groups $\mathop{\rm Aut}(\frak g)\cong\mathop{\rm Aut}(\frak g)_0 \rtimes\pi_0(\mathop{\rm Aut}(\frak g))$.