Basically, where Photoshop is primarily a raster based program (with the exception of the pen tool) Illustrator is a vector based program. This means every shape you make is composed of mathematical algorithms that determine its outline using curves. What this means is that the artwork is scaleable - it doesent ever lose resolution no matter how large or small you make it. It also means that individual elements, or shapes, are saved seperately so that you can always go back and manipulate them.
Illustrator is generally used to do more graphic work, such as making slick advertisement designs and web graphics. However it is very adaptable to need and can be used in conjunction with photoshop. If you wanted to, you could probably use it to design elements for your maps (symbols, compass roses, etc) and them import them to your maps on photoshop. Before I lost my harddrive last week () I was working on my first all-Illustrator map. Its good if you want a really sleek map for conveying information, or you want flat visual effects.
What Illustrator doesent do as well as photoshop is image manipulation. PS has much more in the way of tools for working with preexisting images, and the paintbrush tools tend to feel more organic as well. It is by far the more painterly program. But, like I said, you can import files from one to the other so they compliment each other nicely.