The solution for "general Dehn twist" automorphisms of $Out(F_n)$, namely those which are products of powers of a commuting set of individual Dehn twists, is given in

MR1691946 (2000c:20058) Cohen, Marshall M.; Lustig, Martin. The conjugacy problem for Dehn twist automorphisms of free groups. Comment. Math. Helv. 74 (1999), no. 2, 179–200.

For fully irreducible outer automorphisms, namely those for which no proper nontrivial free factor conjugacy class is periodic, although there is no publication that contains a complete description of the conjugacy problem, nonetheless it is a "folk theorem" that this case is completely covered by the train track technology given in

MR1147956 (92m:20017 Bestvina, Mladen; Handel, Michael. Train tracks and automorphisms of free groups. Ann. of Math. (2) 135 (1992), no. 1, 1–51.

That paper is not written with algorithmic issues in mind, so there are plenty of algorithmic details to fill in. But in outline, given a fully irreducible $\phi \in Out(F_n)$: it is understood that a train track representative of $\phi$ may be computed by following the procedure described in this paper (and there exist several computer implementations); and it is also understood that all of the finitely many train track representatives of $\phi$ (up to topological conjugacy) can similarly be computed; and, finally, this finite set of data is a complete conjugacy invariant for $\phi$.

The solution for "general Dehn twist" automorphisms of $Out(F_n)$, namely those which are products of powers of a commuting set of individual Dehn twists, is given in

MR1691946 (2000c:20058) Cohen, Marshall M.; Lustig, Martin. The conjugacy problem for Dehn twist automorphisms of free groups. Comment. Math. Helv. 74 (1999), no. 2, 179–200.

For fully irreducible outer automorphisms, namely those for which no proper nontrivial free factor conjugacy class is periodic, although there is no publication that contains a complete description of the conjugacy problem, nonetheless it is a "folk theorem" [CORRECTION: see the post of User40911 for an attribution of this to J. Los, as I ought to have remembered since I wrote the MathSciNet review :-/ ] that this case is completely covered by the train track technology given in

MR1147956 (92m:20017 Bestvina, Mladen; Handel, Michael. Train tracks and automorphisms of free groups. Ann. of Math. (2) 135 (1992), no. 1, 1–51.

That paper is not written with algorithmic issues in mind, so there are plenty of algorithmic details to fill in. But in outline, given a fully irreducible $\phi \in Out(F_n)$: it is understood that a train track representative of $\phi$ may be computed by following the procedure described in this paper (and there exist several computer implementations); and it is also understood that all of the finitely many train track representatives of $\phi$ (up to topological conjugacy) can similarly be computed; and, finally, this finite set of data is a complete conjugacy invariant for $\phi$.