At a guess, the Red Army Choir aka. The Alexandrov Choir, which you can hear in many clips on YouTube. For instance, try this clip:
В путь (On the road, or Let's Go!)
http://www.youtube.com/watch?v=A8qakI4mDII
They toured and recorded quite a lot. Then again, if they weren't in uniforms, it was probably some other group, like the Kuban Cossack Choir (did they wear tall fuzzy hats?)

Їхав козак за Дунай (The Cossack rode over the Duna)
http://www.youtube.com/watch?v=9Q-OzsOmi00

And for good measure, one which never fails to choke me up:
Вечер на рейде (Night on the campaign, or Farewell, beloved city).
http://www.youtube.com/watch?v=NJAI5hhsFjI
I'm not sure if the Soviet Choir is a later incarnation of the Red Army Choir or a different ensemble altogether. But I believe it was mainly the Red Army Choir which popularized this song.