A grosso modo a grande diferença é:
Margin / Margem - Espaçamento fora do conteúdo.
Padding / Preenchimento - Espaçamento dentro dos limites do conteúdo.
Os estilos dos elementos HTML estão estruturados dentro de uma caixa chamada de "The Box Model". Dentro dessa mesma caixa existe a hierarquia:
Margin Box
Border Box
Padding Box
Element Box ( O elemento em si, div, span, entre outros )
Tendo em conta que o limite do espaçamento do conteúdo de um elemento é a sua borda (border box). Portanto, a grande diferença neste caso será que a margem é aplicada já fora do elemento e criará espaçamento entre os restantes elementos, porém o padding irá criar espaçamento dentro do próprio conteúdo do elemento, não afetando o espaçamento dos outros elementos.
