Ir embora e ir-se embora são igualmente corretos. Na minha experiência de falante nativo de Portugal, nenhum deles é mais formal ou coloquial que o outro; nem mais bem-sonante que o outro com uma ou duas exceções. Tu foste embora rola muito melhor que tu foste-te embora―aquele te-te é chatinho de articular e não soa particularmente bem. Na prática, na fala relaxada em Portugal aquilo é simplesmente pronunciado como um duplo t, fostt’ embora, que mal se distingue de fost’ embora. Nós fomo-nos embora soa bem, mas dá mais trabalho a articular que nós fomos embora. Já nas outras pessoas, o clítico articula-se muito bem. Eu vou-me embora, ele vai-se embora, eles foram-se embora, etc. rola muito bem: na fala o me e o se enfiam-se ali muito bem entre o verbo e embora. No caso da próclise (clítico ante do verbo; e.g. não me vou embora), a articulação é fácil e bem-sonante em todos os casos.

Com estas ideias eu fui ao Google ver se as frequências das várias frases confirmava a minha intuição: que o pessoal tenderia a evitar foste-te embora, vamo-nos embora, e fomo-nos embora. Confirma mais ou menos. Já que tive o trabalho de coligir aqueles números todos, ponho-os aqui para quem tiver curiosidade.

Alguns padrões que se observam. De uma maneira geral os portugueses são mais adeptos do clítico que os brasileiros. A exceção é no eu vou-me e eu me vou: estas formas são muito usadas quer por brasileiros quer por portugueses; é onde o clítico é mais usado. Depois aquilo que me levou a ir ver estes números. Realmente tu foste-te embora é pouco frequente; nomeadamente, em Portugal, muito menos que tu te foste embora ou tu vais-te embora, o que sugere que de facto aquele te-te afugenta o pessoal.

Com nós, o caso é mais complicado. O clítico é pouquíssimo usado, mas tanto o é após o verbo (onde dá trabalho) como antes do verbo (o que eu não estava à espera). Além disso com a locução pronominal a gente, semanticamente equivalente a nós, o clítico também é pouquíssimo usado, e aí a facilidade de articulação é a mesma que com ele (é vai-se em ambos os casos). Isto leva-me a crer que a razão do baixo uso do clítico com nós terá que ver com outras razões. Omitindo o nós, a frequência do uso do clítico antes do verbo aumenta em Portugal. Por exemplo quando nos fomos embora está a 66% de *quando fomos embora (não está na tabela).

                         Portugal                        Brasil
                   Sem      % de “sem clítico”      Sem     % de “sem clítico”
                  clítico   ênclise  próclise     clítico   ênclise  próclise
Eu vou embora       136       110%      24%         142      163%      41%
Tu vais embora       32        97%      84%         105       19%      18%
Ele vai embora      129        64%      62%         285       40%      16%
A gente vai embora   20        30%       5%         260        2%       0%
Nós vamos embora    120        20%      13%         261        5%       1%
Eles vão embora     102        74%      51%         324        6%      11%

Eu fui embora        87        71%      51%         255       35%       7%
Tu foste embora      50        42%      74%          89       22%      22%
Ele foi embora      159        74%      52%         129       65%      23%
A gente foi embora    7        14%       0%         185        3%       0%
Nós fomos embora     81        10%       6%         217        1%       9%
Eles foram embora    99        77%      47%         306       14%       6%

Chave: Por exemplo, na primeira linha de Portugal, há 136 ocorrências sem clítico (“eu vou 
embora”); com clítico há 150 (110% de 136) ocorrências de ênclise (“eu vou-me embora”) e
32 (24% de 136) de próclise (“eu me vou embora”).