Using stars as a compass
At night, you can navigate after the stars. You should, however, be careful with walking, it is easy to stumble and fall and get injured, and also easy to lose sight of the stars as you go, and you might start going around in circles. Often it will also be more physically and mentally demanding. In the northern hemisphere, there is a star that is almost exactly in the north at all times, the Polaris. It is pretty easy to find, if you know the "Big Dipper". (Everybody knows the Big Dipper (or the Plough)?) Take the two stars at the end of the "Big Dipper", and make an imaginary line "upwards", and extend it five times the distance between the two stars. There you have it - Polaris. That way is always north. The figure is courtesy of Kathy Miles. Used with permission.

In the southern hemisphere, you would have to find the Southern Cross. Because I haven't been south of the equator, I can't help you find it, make someone tell you where it is right now, if you don't know it already. That way is south.
If you have an analog wrist watch, you can use the time to find north. Hold your watch up in front of you, and let the short hand, red on the figure, that indicates hours point at the sun. While holding it like this, cut the angle between the red arrow and 12 o'clock in two, (noonwards if the time is before 6am or after 6pm), that way is south. (The reason you need to cut it in two, is because the clock takes two rotations while the sun takes one around the earth, it is of course the other way around, but never mind.)

Many people wear digital watches these days (I do myself, if I wear one at all). If you do, draw an analog watch face on a piece of paper, and then mark the hour hand on using the digital watch. The rest of the method is identical.

This method can be used even when it is pretty foggy. Although you may not be able to see the sun, it may still cast a shadow. If you take up a straw or a tiny stick, and you may see a shadow. You just have to remember that the shadow points the opposite way from the sun, but the rest of it is quite similar as above.