I'm not sure about this, so please correct me (or just downvote?).

Given a non-square discriminant $D$, find it's square part: $D = ab^2$ ($b$ largest possible). So $F = \mathbb{Q}(\sqrt{a})$ is the quadratic subfield of the $S_3$ closure, and the closure is a cyclic extension of this. Hence, by class field theory, it corresponds to a ray-class of order 3 in some ray class group of $F$.

There are two cases now:

1. If $b=1$, then the ray class must correspond to a class in the class group of $F$. So, compute the class group of $F$, and for each class of order 3 there's a cubic extension of the quadratic field. This will be the closure of your desired cubic over the rationals, so just look for the cubic subfield.

2. Otherwise, the corresponding class cannot be in the class group itself. Instead it must be in a ray class group of modulus $b$ (is this true?). So, compute the ray class group of modulus $b$, and for each class of order 3...

This algorithm has subexponential complexity in $D$. To learn how to compute class groups of quadratic fields:

"Computational Algebraic Number Theory", H. Cohen

To learn how to compute ray class groups and how to find fields corresponding to classes:

"Advanced Topics in Computational Number Theory", H. Cohen

I'm not sure about this, so please correct me (or just downvote?).

Finding fields of a given discriminant has two main algorithms, depending on the context. If you want to find all fields up to a certain discriminant in order to build a table, this is done using theorems for bounds on the coefficients of a minimal element. This direction, particular to cubic fields, is one of the chapters in the Advanced book mentioned below. If you want to find all fields of a given (large) discriminant, there's the following.

Given a non-square discriminant $D$, find it's square part: $D = ab^2$ ($b$ largest possible). So $F = \mathbb{Q}(\sqrt{a})$ is the quadratic subfield of the $S_3$ closure, and the closure is a cyclic extension of this. Hence, by class field theory, it corresponds to a ray-class of order 3 in some ray class group of $F$.

To settle the correct ramification, the ray class group must have modulus $b$. So, compute the ray class group of modulus $b$, and for each class of order 3 there's a cubic extension of the quadratic field. This will be the closure of your desired cubic over the rationals, so just look for the cubic subfield.

This algorithm has subexponential complexity in $D$. To learn how to compute class groups of quadratic fields:

"Computational Algebraic Number Theory", H. Cohen

To learn how to compute ray class groups and how to find fields corresponding to classes:

"Advanced Topics in Computational Number Theory", H. Cohen