Let $S$ be a smooth cubic surface defined by $f\in \mathbb Q[x,y,z,w]$. Is there an algorithm to write down the 27 lines on $S$? Or at least find a field extension of $\mathbb Q$ over which these lines are defined?

This work from the Mainz Algebraic Geometry Group may help:
Here is a little snippet from p.6 (of their Dagstuhl article). They take as input six points $\{P_1,\ldots,P_6\} \subset \mathbb{P}^2$ in the plane in general position: 


Once you have the six points in $\mathbb{P}^2$, there is a very easy algorithm to give the cubic surface and the $27$ lines. First, the map to $\mathbb{P}^3$ corresponds to cubics through the six points. So you can choose reducible ones (union of three lines through $2$) and get generators $(f_0:\dots:f_3)$. Then, you find the equation by putting the $f_i$ into a polynomial of degree $3$ and solving the linear equation on the coefficients. Then, the $27$ lines are the strict transforms of lines through $2$ points, conic through $5$ points and the exceptional divisors. If you have the points and the $f_i$, this is algorithmic. To simplify your calculation, you can choose the points and choose (over an algebraically closed field) $[1:0:0]$, $[0:1:0]$, $[0:0:1]$, $[1:1:1]$, $[1:a:b]$, $[1:c:d]$. The only nonalgorithmic part is starting from the cubic to find the contraction to $\mathbb{P}^2$. This corresponds to find lines on the cubic and is then more complicated (and there is in general no solution with radicals, as explained by David Speyer). Note that the same kind of algorithm works with del Pezzo surfaces of degree $4$, $2$, $1$. I did it often with Maple with points given. 


Here is yet another place to look for an algorithm: you can find a description of how to compute homogeneous equations for the Plücker coordinates of the lines on a cubic surface in the Macaulay 2 tutorial at What you will find there is essentially is the same procedure as in Jim Carlson's Sage code mentioned in the comments above, but perhaps it is a bit easier to read. The tutorial also discusses the general problem of computing equations for the Fano variety (scheme) of a projective variety. 

