Куда следует обратиться для легализации брака, если он был заключен в другой стране?

Здравствуйте! поскольку Испания является участником Гаагской конвенции и в сертификате о замужестве у Вас уже стоит штамп  «апостиль» то дополнительно легализовывать брак нет необходимости. 

Легализация брака с иностранцем производится путем легализации документов через проставление штампа «апостиль» либо через консульскую легализацию.
 
По общему правилу браки между гражданами РФ и иностранными гражданами, заключенные в другом государстве с соблюдением его законодательства, признаются действительными в РФ. Иными словами, нет необходимости легализации самого брака. Но может понадобиться легализовать документы, подтверждающие брак с иностранцем (ст. 158 СК РФ; ст. 13 Закона от 15.11.1997 N 143-ФЗ).
  Упрощенная легализация (проставление на документах штампа «апостиль»)
Проставление штампа «апостиль» применяется для использования документа в странах, присоединившихся к Гаагской конвенции (Конвенция, отменяющая требование легализации иностранных официальных документов, заключена в Гааге 05.10.1961).
Так, например, если брак с иностранцем заключен в Испании (страна — участница Гаагской конвенции), то для легализации брака в России будет достаточно, чтобы официальное учреждение Испании проставило на документах о браке штамп «апостиль». После этого документы о браке будут действительны на территории России (ст. ст. 3 — 6 Конвенции).
Если у вас есть документы о браке с иностранцем, на которых проставлен штамп «апостиль», то вы должны в РФ сделать и удостоверить перевод таких документов в нотариальном порядке. Удостоверенные у нотариуса документы о браке, заключенном в другой стране, можно будет использовать в России (ст. 81 Основ законодательства РФ о нотариате, утв. ВС РФ 11.02.1993 N 4462-1).