It depends on the part of the sky you're viewing as well as the focal length of the lens you're using. While objects near the celestial equator appear to move at the earth's rotation rate of 15 degrees per hour, their apparent rate of motion decreases to zero at the celestial poles. As a result, it takes longer for star trails to become noticeable at high celestial latitudes than near the equator. Additionally, the magnifying effect of telephoto compared to wide-angle lenses will make star trails more obvious.

In terms of actual exposure times, one source gives 30 seconds as the maximum exposure with a 20-mm lens and 12 seconds with a 50-mm lens. This progression appears to follow the formula

maximum exposure time in seconds = 600 / focal length in millimeters

http://www.digital-photography-tips.net/beginners-photography-night-sky.html

Presumably, these figures are for objects near the celestial equator, and longer exposures would be possible for objects near the poles.

The following link includes images taken using an 18-mm lens with exposures of 80 and 152 seconds. Note that 600/18 = 33.3, so even the 80-second exposure is 2-1/2 times longer than that suggested by the above guidelines; trailing is noticeable but slight (these images are of the central Milky Way, with celestial latitudes ranging from about +10 degrees at the top of the image to -40 degrees near the horizon) and suggests that these exposure guidelines are fairly accurate and perhaps even a bit conservative, especially for objects at high celestial latitudes.

http://digitalphotographyblogs.com/2008/07/30/capturing-the-night-sky-the-milky-way/
http://www.hawastsoc.org/deepsky/sgr/sgr.html

An image of the moon, close up, and night sky will show blur (or a 'star trail') at any exposure over 6 seconds. In general the earth rotates at a rate that translates to about a 15 second exposure - the wider your lens (say 17mm versus 70mm) the more forgiveness you'll have before you start to see a 'trail' of stars or blur in the sky.

Any night time photography in my opinion needs a tripod (regardless of vibration reduction lenses or camera technology), and a timing mount is up to you depending on the effect you wish to obtain.

For some really great night sky photography tips and tips for photographing stars go here:
http://www.danheller.com/star-trails
or here:
http://howto.wired.com/wiki/Photograph_the_Stars

Happy shooting...

That really depends on how stable your hand is, and whether you have anything to put your camera against. In general, any nighttime photography using an exposure of more than 0.5 seconds REALLY needs a mount, and even then you need to use the timer to ensure the camera is stable while taking the photograph. Anything between 0.3 and 0.5 seconds
Any outdoor nighttime protography (without flash), benefits tremendously from using a mount, and will improve greatly this way.
Make sure there is no belt swinging, the mount is stable, and then use the timer to ensure best results.