Right: 14 minutes, f/5.6, ISO 320 at 45mm. This shot was taken just before dawn allowing some colors to creep in.
Go where there are stars
The first requirement for star shots is probably obvious: you need to go somewhere where you can see the stars! In general, this means away from the city and its corresponding light pollution. Higher elevations are generally better as well. There should be minimal to no cloud cover (though clouds can add interest for general night photography). Bland skies with no clouds generally make for uninteresting sunset and sunrise photos, but they're perfect for stars.
Start shooting when it's completely dark
An hour after sunset is usually too soon. An hour before sunrise is usually too late. In general, you'll want to shoot between astronomical dusk and astronomical dawn, when the sky is at its darkest. It's also best to shoot when there is no visible moon. Of all the rules, this one is meant to be broken. It is possible to take star shots with the moon, as long as it is out of your frame and is front lighting your subject (the stars will just be more subtle) such as the Yosemite Falls shot above. It's also OK to take shots as twilight transitions to night and night transitions into twilight (in fact, this can be a great way to get a little color in the sky, such as the shot in this section taken just before dawn).
Buy a remote timer or remote switch
For still star shots, where the exposure time is under 30 seconds (the typical maximum exposure time allowed in camera), you can get away without either of these, but they will make your life much easier. Prefer a remote timer over a remote switch, even though they're more expensive, as it will allow you to specify the exposure time and shoot continuously which is very handy for star trail shots.
Carry an extra (charged!) battery
The combination of long exposures and typically cold temperatures necessary for star trails shots drain batteries quickly. If you plan on combining your night photography with a sunset or sunrise (or both!) having an extra battery around is essential.
Bring a flashlight or headlamp
This will make it easier to see your camera, adjust the focus and other settings, and even better, find your way back to the trail head.
Keep your camera warm
If you are shooting exposures over 10 minutes at night, your camera may become colder than the air around it, causing the relatively warmer air to condense on the colder camera, so it's important to at least try to keep the camera warm. How? One technique that seemed to work was rubber banding hand warmers to the lens and wrapping the camera in a towel. Another possibility would be a battery powered hair dryer that you fire at regular intervals. Astronomers face the same problems with telescopes and they have specialized equipment for dealing with it, though some of it is quite pricey.
Use manual focus and manual/bulb exposure modes
When it's dark, auto-focus doesn't work, so use manual focus. Exposure meters are also often incorrect at night (sometimes varying wildly from shot to shot) so you should use manual exposure mode (for still shots or test shots), and bulb exposure mode for shots over thirty seconds. When shooting in bulb exposure mode, be sure to disable mirror lockup.
Use the histogram, not the LCD
When your eyes adjust to the darkness, images on the LCD may appear brighter than they actually are, the histogram is a more reliable representation of the exposure.
Remember, star photos are landscape photos too!
This means that you still need to be concerned with composition, subject, and sharpness. Unless you have a bright moon, it's very difficult to see at night, so it helps if you're familiar with the area and already have a composition in mind.