A proof by contradiction is a good approach. Suppose you have a quadrilateral $ABCD$ whose opposite angles are supplementary, but it is not cyclic. The vertices $A,B,C$ determine a circle, and the point $D$ does not lie on this circle, since we assume the quadrilateral is not cyclic.
Suppose for instance that $D$ lies outside the circle, and so the circle intersects $ABCD$ at some point $E$ on $CD$ (try drawing a picture to see this if needed.) Now $D$ is supplementary to $B$, and since $E$ is the opposite angle of $B$ in the cyclic quadrilateral $ABCE$, $E$ is supplementary to $B$ by the theorem you already know, and so $D$ and $E$ are congruent. But this contradicts the fact that an exterior angle cannot be congruent to an interior angle, which proves the converse. A similar method works if $D$ lies inside the circle as well. (I abuse notation a bit and refer to a vertex and the angle at that vertex by the same letter.)