On a basic level, すみません is to apologize for something that you have a "right" to do, such as when passing through a crowd or getting a waiter's attention at a restaurant. ごめんなさい, on the other hand, is for when you have done something inappropriate. So on the way through a crowd, you would say すみません to ask people to let you through, but if you accidentally step on someone's foot along the way, you would use ごめんなさい to apologize.
Incidentally, すみません is also for saying "thank you" when someone has gone to the trouble of doing something for you, such as pouring a cup of tea. Although some Japanese may consider it more honest (素直【すなお】) to simply say ありがとう, すみません ("I apologize [for having caused you to go to the trouble of doing this]") is the more natural Japanese response in these situations.
申【もう】し訳【わけ】ありません (or 申【もう】し訳【わけ】ございません) is a more formal version of ごめんなさい which literally means, "There is no excuse." Often you'll hear it at press conferences when the latest company president to be caught up in some scandal has to publicly apologize with a deep bow in front of the flashbulbs.
Both すみません and ごめんなさい have informal versions: すまん (or すまない) and ごめん. The usage rules stated above do not change with these versions, but as with as with all informal constructions, you should reserve them for casual settings or situations where your position is above that of the listener's.
