What style are you going for? If you can find an example(s) somewhere on the web and drag the link over here, that will help people to explain how to go about it.
On a software note, another good free program that can help with city maps is google sketchup. I like to use it to build basic shapes in 3D to get the perspective correct, and shadows if required, and then export a screenshot over to photoshop to do the actual drawing of the map. It has good start up tutorials and is pretty simple to learn. But if you want just a 2D map, then I'd recommend using shape tools/path tools and/or holding the shift key down (in ps, I think gimp is the same) to get straight lines.
If you don't have a clue what you want for a city layout (map before story option) then you can get some pretty interesting ideas from inkblots on those cheap little giftbox pads. But save that for when you're really hard up for ideas; it's not as straightforward as it might sound.
There is also a sub-forum on here for requesting maps, if you get truly fed up.