What lens should I consider after the 18-55mm kit lens for landscapes and sky photos on a Nikon D5100?

To make sky and landscape photography, you would better buy a wide-angle lens. See this link for a lens simulator that shows this visually. Try to find your working range with it, and then look for similar lenses.

I think you should stick to a single focal length, as you will notice that as soon as you have a wide angle, you pretty much operate it on the lowest focus length.

(I have recently tried a Tokina 11-16 DX II, and I loved the quality of pictures. I am planning to put up some eventually. Actually, I rented this from LensRentals.com, just to try out if I need this or a different lens, and probably I am going to buy one for the DX camera.)

Now, if you need zooming, I think the kit 18-105 is an extremely beautiful piece of lens for the price. Good overall performance, not excessively heavy, pretty reliable.

UPDATE: because the link of yours did not work the first time: definitely, you can use the 18-105mm for this type of photography. This is neither sky nor landscape though... :-)) He mostly does shallow DOF with some nice background. You can use the 105mm end for this photos, or use a fixed focal length lens with wide aperture. E.g. starting from 85mm 1/1.8.