As already mentioned:
Tschuldigung seems to be the word you heard.
Sorry is also very common,
Verzeihung is another possibility. (I'm from South Germany and I wouldn't use it. But I think it is used in other parts Germanys)
In Switzerland you may hear also éxgüsee or Exgüsi (from the French excusez).
Sometimes I heard a 'Pardon` (French pronunciation).