This is quite a big question, as it pertains not only to the particular situation, but also the level of politeness it calls for. Here's a cursory overview as I see it. This is just off the top of my head, and I'm not a native speaker, so take it with the appropriate amount of salt.
suman/sumanai: frankly, I practically never hear this. Maybe between close friends? (also, I pretty much never see this or sumimasen in kanji) Your mileage may vary.
gomen [+ne]: common, quick, casual. pretty useful and common amongst good acquaintences.
sumimasen: more polite, good for accidentally bumping passers-by, or calling to a waiter/waitress. Can also be used as a thank you. suimasen is the same thing, though I've only heard it in kansai. I probably use this the most.
gomen nasai: even more polite yet, probably about as formal as one needs to get in most daily situations for an exchange student or tourist. (again, rarely see kanji for it)
moushiwake nai/omoushiwake arimasen/omoushiwake gozaimasen: They are all the same apology, with differing levels of formality. Literally "I have no excuse," it's probably the most polite phrase that equates to an apology. I use it when I feel that I've really inconvenienced someone.
ojama shimasu and shitsurei shimasu are more like kimarimonku (set phrases) than apologies. As examples, ojama shimasu would be something you say when you enter someone's home, and shitsurei shimasu would be something you say when you enter a professor's office, or end a phone call. Past tense forms are used as well, when leaving someone's home or office.
御免なさい for my amateur explanations!!
