I'll second that, Terragen is really easy to make skyboxes with. I did a load of work with the Torque engine and as a part of that, I had to make skyboxes for my levels. Terragen did a wonderful job. Only thing was (my version) didn't do trees and so on. I did find the tutorial I used, but Sascha has it covered.

Just checked the Terragen site, and DAMN! Terragen2 is lookin' fine
http://www.planetside.co.uk/terragen/

http://www.planetside.co.uk/gallery/v/tg2gallery/

I think I've got a utility for rendering starfield skyboxes on my machine at home. If you need it, I'll have a look for it. The original page has gone though.