I have to recommend a combination of [mouviciel][1] and [jrista][2]'s answers.

You want to use a fast lens, which will allow a shorter shutter speed. This is absolutely necessary if you are going to shoot handheld. Since you only have the kit lens, you should certainly go ahead and get the <a href="http://www.amazon.com/gp/product/B00007E7JU?ie=UTF8&tag=phot0b7-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=B00007E7JU">Canon EF 50mm f/1.8 II</a><img src="http://www.assoc-amazon.com/e/ir?t=phot0b7-20&l=as2&o=1&a=B00007E7JU" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" />, which is about the best lens you'll find under $100 US.

You will also (if you have a choice) want to shoot in the first hour past sunset or the hour before sunrise for the best lighting.  During these times there is more light, but you still have the nighttime feel.

Other thoughts:

 - When I'm trying to get a nighttime feel, I use a little different pattern than usual:

   + I try to adjust the color a bit to the cool side, which I think generally hels the mood
   + I slightly under-expose (about 1 stop).  Remember that your camera is trying to adjust to about 18% grey (maybe a little different with digital), so it is going to try to make a dark scene just as bright as a midday sun scene.  By slightly under-exposing you can increase your shutter speed and avoid the blur.

 - Go ahead and bump up the ISO. This will cause more noise, but you will want to take that hit to get the higher shutter speed you need to get a clean shot. ISO noise can be dealt with in post, whereas camera shake can't be fixed.

 - Take a look into different [hand-holding techniques][3].


  [1]: https://photo.stackexchange.com/questions/3880/how-to-take-great-night-shots/3892#3892
  [2]: https://photo.stackexchange.com/questions/3880/how-to-take-great-night-shots/3883#3883
  [3]: https://photo.stackexchange.com/questions/178/techniques-for-hand-held-image-stabilization