Well, "conjugation by $a$" shuffles the elements of $G$: each $g$ goes to $aga^{-1}$, right?
There are two possibilities: (i) if $a$ happens to commute with every element of $g$, then $aga^{-1}$ is the same as $gaa^{-1} = g$, so the "shuffling" is just the identity. (ii) If not, then some element $g$ is sent to a different element, and the shuffling is nontrivial.
So not every element $a$ of $G$ leads to an interesting shuffle: only the ones that fail to commute with at least one other element. So you might think that the inner automorphisms would correspond to $G - Z(G)$. But in fact, if $a$ produces an interesting automorphism, $\phi$, but $b$ produces the identity, then $ab$ will also produce $\phi$. So really the right correspondence is with $G/Z(G)$.
Does that help at all?
Let me add a concrete example: Suppose that $G$ is the group of all rotations and dilations of 3-space, where the rotations leave the origin fixed, and by "dilations" I mean maps like $\mathbf v \mapsto c\mathbf v$, where $c$ is a nonzero scalar. Then the subgroup $D$ of dilations is the center of $G$: if you scale up, rotate, and then scale down, it's the same as just rotating. And if you scale up by $a$, then by $b$, then by $1/a$, it's the same as scaling just by $b$.
And $G/D$ looks just like $SO(3)$ (i.e., the group of origin-fixing rotations of 3-space, known as the "special orthogonal" group -- "orthogonal" because the matrices are orthogonal; "special" because their determinant is $+1$). Why does this correspond to the inner automorphisms of $G$? Because each rotation $R$ corresponds to an automorphism of $G$, namely, the change of basis induced by $R$.
I don't know if that helps clarify things or not, but it was worth a shot...
Here is a "geometrical" way of looking at $\text{Aut}(D_4)$.
In this view, it should be clear that a generating rotation has to map to another generating rotation, and a generating reflection has to do the same. This gives us $8$ (at most) possible automorphisms:
$r \mapsto r,r^3$
$s\mapsto s,rs,r^2s,r^3s$
(just "mix and match").
Now, geometrically, sending $r \to r^3$ "reverses" the direction of the rotation, as if we had reflected about the $x$-axis (for example). That is, there is a natural association of $\sigma_s$ with $s$ (using Aaron's notation).
What is the geometrical result of sending $s \to rs$ (and leaving $r$ fixed)? It changes the axis of reflection, that is, it corresponds to the rotation $r$. If we call this automorphism (first, you might try proving it IS one) $\rho$, it isn't hard to see that $\rho$, like $r$, is of order $4$.
Now all that remains to be done is show that $\text{Aut}(D_4) = \langle \rho,\sigma_s\rangle$, that $\sigma_s\rho = \rho^{-1}\sigma_s$, and that the $8$ automorphisms obtained this way are all distinct.
(There's nothing I can add to Aaron's elucidation of $\text{Inn}(D_4)$, except to remark that $D_4/Z(D_4) = D_4/\langle r^2\rangle \cong V = C_2 \times C_2$).
Best Answer
Consider the map $\phi:G\to\text{Aut}(G)$ defined as $\phi(g)=\varphi_g$, where $\varphi_g$ is the automorphism of $G$ defined by $\varphi_g(h)=ghg^{-1}$.
Lemma 1: $\phi$ is a homomorphism.
Proof: We have $\phi(g_1g_2)=\varphi_{g_1g_2}$, and $$ \varphi_{g_1g_2}(h) =(g_1g_2)h(g_1g_2)^{-1}=g_1(g_2hg_2^{-1})g_1^{-1}=\varphi_{g_1}(\varphi_{g_2}(h)).$$
Lemma 2: $\text{ker}(\phi)=Z(G)$.
Proof: We have $$\begin{align*}\text{ker}(\phi) &= \{g:\phi(g)=e\} \\ &= \{g:\varphi_g=e\}\\ &= \{g:\varphi_g(h)=h\} \\ &= \{g:gh = hg\} \\ &= Z(G).\end{align*}$$ Finally, by the first isomorphism theorem, we have $G/\text{ker}(\phi) = G/Z(G)\cong im(\phi) = \text{Inn}(G)$, as desired.