Lars
You have received a lot of excellent advice, the main point is learn your machine and what means are available on it to adjust for turning parallel.
Just for a point of reference. I have three lathes and let me tell you what I do twice a year ( December, May) to each one. First the machines are in an insulated heated and air conditioned building on 6" insulated concrete floor. All leveling is done with a Starret Master 199 level.
The 15" x 50 " Triumph 2000 Colchester is old, 1978, and just a little worn. I first level the lathe. I then use a 2" x 6" bar with rings and tweak the headstock adjustment until they turn to within .0003/4. I check the tail stock with a center in the headstock and a center in the tailstock. Run them close and put a my 6" rule in between the centers if it stays nice and straight I am done otherwise I adjust the tailstock. I do not do any further adjustment to the tailstock because if I am going to turn between centers I have a test bar that I use and carefully adjust it at the time of use.
The 12" x 24" Clausing 5904 was virtually brand new when I got it in 1996. Bed is real nice. I level it first. I use a 1" x 6" bar with rings and tweak this to .0001 or less depending on my patience. Same test as above for the tailstock. I use this lathe about 75% of the time. So it gets checked if I need something really close for a job. This lathe stays put pretty good.
The 7" x 19" Myford Super 7B was brand new when I got it in 1981. I level it first. I use a 1" x 6" bar with rings and get this to .0000. I use this machine with collets often and want it as close to dead nuts as possible. I use a test bar between centers to set tailstock as I want it dead on. This machine is not real robust but it holds setting OK for what I use it for ie not hogging off metal.
Now all of the above means nothing if the material is not supported, and the cuts being taken are not appropriate for the material, the machine, the feed, the speed, the cutting fluid, etc.
By the way I have two milling machines, a band saw, a grinder, and one drill press that all get similar treatment.
May sound like a lot of work but if you do it regularly it actually takes very little time. I do the whole shop in a day including milling machines, a band saw, a surface grinder, and drill press. Not to mention small machines like drill sharpener, sander, die filer etc.
I have been doing the above for over 30 years and it is a pleasure to walk up to a machine and get the result you want first time (well assuming no operator error!).
Bob