Generalization of cycle decomposition to Coxeter groups
Following Nathan's advice let me elaborate a bit on my comment and also provide an answer.
As pointed out it is not true in general that any element $w$ in a finite Coxeter group is a Coxeter element in some reflection subgroup (see the counterexample above).
Actually I have been thinking recently about this question of generalizing the cycle decomposition to arbitrary finite Coxeter groups and here is how I did it. I am stating the result here and briefly explaining. The details and proofs can be found on a preprint which I just put on my webpage http://www.mathematik.uni-kl.de/fileadmin/AGs/agag/gobet/ex/cycle.pdf (it will appear on arxiv soon but there is some additional stuff which I have not written yet which will be added).
Any element $w$ in a finite Coxeter group $(W,S)$ has a generalized cycle decomposition in a suitable sense, but unicity fails in general. It works as follows.
Let $(W,S)$ be finite and let $w\in W$. Denote by $T$ the set of reflections of $W$, that is, the set of all conjugates of the elements of $S$, and by $\ell_T$ the length with repect to the generating set $T$ and by $\leq_T$ the absolute order on $W$ induced by $\ell_T$. Write $\mathrm{Red}_T(w)$ for the set of reduced $T$-decompositions of $w$ (i.e., smallest length factorizations of $w$ as products of reflections). I denote by $P(w)$ the parabolic closure of $w$, that is, the smallest parabolic subgroup containing $w$. I am considering the following condition on $w$:
(Condition A) There exists $(t_1, \dots, t_k)\in\mathrm{Red}_T(w)$ such that the reflection subgroup $\langle t_1, t_2, \dots, t_k\rangle$ is parabolic.
Then I claim the following
Theorem [Generalized cycle decomposition] Let $w\in W$ satisfying Condition A. Then there exist $x_1,x_2,\dots, x_m\in W$ such that
$x_i x_j= x_j x_i$ for all $i, j=1,\dots, m$,
$w=x_1 x_2\cdots x_m$ and $\ell_T(w)=\ell_T(x_1)+\ell_T(x_2)+\cdots+\ell_T(x_m)$,
Each $x_i$ admits a reduced $T$-decomposition generating an irreducible parabolic subgroup $P_i$ (in fact, $P(x_i)$) of $W$ and $$P(w)=P_1\times P_2\times\cdots\times P_m=P(x_1)\times P(x_2)\times\cdots\times P(x_m).$$
Moreover, such a decomposition of $w$ is unique up to the order of the factors.
In the case of the symmetric group of course the $x_i$'s are just the cycles occuring in the cycle decomposition of $w$. Moreover in type $A$ every element satisfies Condition $A$.
Now let me say a few words about elements for which Condition A fails. In fact, elements satisfying Condition A above are the so-called "(parabolic) quasi-Coxeter elements", which we characterized together with Baumeister, Roberts and Wegener as the elements $w$ for which the Hurwitz operation is transitive on $\mathrm{Red}_T(w)$ in this paper http://www.degruyter.com/view/j/jgth.ahead-of-print/jgth-2016-0025/jgth-2016-0025.xml which Christian pointed out. Now if $w$ does not satisfy Condition A, it precisely means that the Hurwitz operation on $\mathrm{Red}_T(w)$ has several orbits. Taking a reduced expression of $w$ in one of the orbits, $w$ is a quasi-Coxeter element in the reflection subgroup generated by the reflections in this reduced expression (which, as any reflection subgroup, is a Coxeter group), hence $w$ has a generalized cycle decomposition in that subgroup. In this situation $w$ will have as many generalized cycle decompositions as the number of Hurwitz orbits on $\mathrm{Red}_T(w)$.
So in fact, somewhat surprinsingly, any (parabolic) quasi-Coxeter element (as the element in $D_4$ above which yielded a counterexample to Nathan's claim) still has a generalized cycle decomposition (I mean: including unicity). The obstruction to unicity comes from elements where no $T$-reduced expression generates a parabolic subgroup, such as for instance the longest element in type $B_2$.
Finally, note that this heavily requires properties which only hold in finite Coxeter groups (such as the characterization of parabolic subgroups as centralizers of subspaces), hence I have no idea about possible generalizations to arbitary Coxeter groups... It would be very interesting to be able to characterize parabolic subgroups as centralizers of subspaces in a suitable faithful representation of $W$ in the infinite case...
EDIT: I realized that Brady and Watt is not needed for unicity - unicity is already clear from the direct product decomposition.
I think the most general thing you can say is the following: Any element $w$ is the Coxeter element of a reflection subgroup (a subgroup generated by reflections). To show this, write a "reduced $T$-word" $t_1t_2\cdots t_k$ for $w$ (a shortest possible word for $w$ as a product of reflections). Note that the usual notion of a reduced word is different, as it uses only simple reflections. One can show (for example, I think this is in Drew Armstrong's AMS Memoir) that $w$ is a Coxeter element in the reflection subgroup generated by the $t_i$.
UPDATE: This answer is wrong. For now, I'm leaving it here so that the comments---which point out why it is wrong---will make sense, and so everyone will know to down-vote it :).
I had gotten concerned when I couldn't actually find this in Armstrong and was looking for a proof. Thomas' counterexample below puts that effort to rest.