Like the above poster wrote... a tripod is what's going to make the difference between a very sharp night photo and one that's a little (or a lot) blurry. You'll also need a remote shutter release, or to use the 2-second timer (to prevent camera shake from pressing the shutter button.) You can also try to stabilize the camera on a solid surface, or use a beanbag or really, anything that will hold the camera steady, and you will generally get better results than handholding.
Really, the important thing is to get enough light into the camera for a proper exposure. Using a tripod allows you to use a let more light in by holding the shutter open longer.
Checking your flicker site, that photo (or one just like it) was taken at ISO 800, F5, and 5/8th of a second. That's an awfully long time to handhold the camera. I'm guessing that you were using the kit 18-55mm lens, so no image stabilization, either. If you want to get a sharp photo without using a tripod, you either have to use a larger aperture (the opening in the lens) or make your camera more sensitive to light (the ISO).
Your ISO is 800, which is already fairly high. You can go up to 1600 but you'll find the picture starting to get a little "noisy". This bothers some people more than others, but your camera should be capable of pretty decent ISO 1600 shots.
Your aperture, on the other hand, is fairly small. This is mostly likely due to the lens - I'm pretty sure the camera was automatically trying to get the biggest opening it could, but kit lenses are just not designed for low-light work. For comparison, an F2.8 lens (if my math is right) is 1.5 stops brighter than your lens at F5, and an F1.4 lens is 3.5 stops brighter. Each stop is double or half as much light as the next stop. A faster lens will allow a much faster shutter speed, minimizing the chances of blurriness due to hand shake.
An image stabilized lens would help, too - but ultimately, a tripod is a big key.
