Angelo has indicated the most classical type of counterexample involving two semisimple elements of $\mathrm{PGL}_n$, but the question warrants some further discussion. Though it is posed (and maybe motivated?) over $\mathbb{C}$, the natural setting is a *connected* reductive algebraic group $G$ over any algebraically closed field. If you start with two commuting elements, one of them can be viewed as lying in the centralizer of the other: a closed but not necessarily connected subgroup. So centralizers are involved here in an essential way. Working with arbitrary elements may get rather complicated, since for example the study of centralizers of unipotent elements tends to require case-by-case study.

So consider just two commuting semisimple elements $s,t$ of $G$. The question is when they both lie in a *proper* parabolic subgroup. If $G$ is just a torus, there are no nontrivial proper parabolics. Otherwise $G$ has a nontrivial semisimple derived group. Now we might as well assume $G$ itself is semisimple (of rank at least 1), because the center of a reductive group lies in every maximal torus and hence in every parabolic subgroup.

From the standard structure theory of $G$ (Chevalley, Borel-Tits, Springer, Steinberg), the structure of the centralizer $C := C_G(t)$ of any semisimple element $t$ is understood: $C$ is reductive of maximal rank and is connected whenever $G$ is *simply connected* but otherwise sometimes not. In general any semisimple element lies in some maximal torus of a given reductive group. As a result (see Springer-Steinberg reference in my comment above), when $G$ is simply connected both $s$ and $t$ lie in a maximal torus of $C$ (hence of $G$; this in turn lies in a Borel subgroup, which is a proper parabolic subgroup of $G$.

On the other hand, when $G$ fails to be simply connected, as in Angelo's example (for $n>1$), Springer and Steinberg observe that the group $C$ will typically not be connected for some $t$ (taking some care in prime characteristic about the separability of the universal covering map for $G$). Thus if $s$ lies outside the identity component of $C$, one may have trouble fitting both $s$ and $t$ into a *proper* parabolic subgroup (though I'm not sure how to construct counterexamples other than case-by-case). In Angelo's case, the problem is that the permutation matrix chosen represents the longest element of the Weyl group, which by the Bruhat decomposition won't lie in such a parabolic along with $t$.

ADDED: To respond to Adam's last sentence (where "proper parabolic" is intended), rank 1 is not the problem but rather the fact that his group fails to be simply connected. His special orthogonal group (Lie type $B_1 = A_1$) is just a matrix realization of the 3-dimensional irreducible representation of $\mathrm{SL}_2(\mathbb{C})$: the adjoint representation using an orthonormal basis of the Lie algebra relative to its Killing form. This adjoint group is isomorphic to $\mathrm{PGL}_2(\mathbb{C})$, while his commuting pair of semisimple elements is a special case of Angelo's example. Here the centralizer of one element corresponds to the group of monomial matrices, with a Weyl group representative outside the identity component. This disconnected group fails to lie in any Borel subgroup, here the only type of proper parabolic.