I've been looking for a program that can create maps on a Mac... Any ideas? I would like it to be a World Map, that the players just relate to, to know where they are and to tie all of the quests into one story. Also as a side note, I'm not skilled at GIMP or Photoshop, so I would rather not go on that approach.
Nearly all mapmaking software aimed at RPGs is exclusively for Windows, which makes it hard for GMs who are Mac owners to find anything to create maps, if they don't have the technical and artistic skills that mapmaking with a photo-editing suite requires.
The one RPG mapping tool I've used to good effect that is available on Mac is Hexographer. (It's Java, so runs everywhere Java is installed, which includes Macs.) I've used its free verson to create world maps before, and it does the job well enough. It creates hex maps though, so its maps are not pretty by modern standards (unless you like the aesthetic of hex maps!), but for your purposes will convey the information you need to your players.
When I saw the question I immediately thought of Hexographer.
I use it on a Windows PC and Linux (runs under Java, so should also work on Mac). The free version has good random map generation, but also a good choice of tiles to create your own from scratch.
The paid version lets you zoom in on a hex (or range of hexes) to add more detail to a specific area, also an option to import an image (such as an outline map) and draw on top of it.