Chris a bien expliqué toutes les nuances liées à ces expressions. Le mot passe-partout est "pardon". Ce n'est pas trop long, et c'est d'un niveau de langage tout-à-fait correct. "Excusez-moi" pourrait parfois être mal perçu, puisque l'expression utilise l'impératif. A mon avis, "je m'excuse" ne veut rien dire. 

If you want to be very formal, you could say "Je vous prie de bien vouloir m'excuser" ou "je vous prie de m'excuser".

Never say "je m'excuse" even if we use it unfortunately. That's not correct.

"Pardon", "Désolé" and "Excusez-moi" are more or less formal but often used, even in a formal way, but always verbally, not in a letter for example.

Désolé is also used if someone requests you something (a coin or a cigarette for example): "Désole je n'ai pas d'argent".