Formally, please say them together. In casual speaking, you can say "Arigatou" alone. I agree with Richard mostly, except the meaning of "welcome." In case of saying "you're welcome" in reply to "Thank you," we say "Dou itasimasite." This ordinary word for a gratitude is often simply translated to "Thank you very much" in English. Most Japanese words and Kanjis have etymology. "Arigatou" =　originally, "Arigatai or Arigatashi"　means that it is rare to have, see, hear, or be given something. "Gozaimasu" =　originally said like, ”gozaru + masu” →"Gozarimasuru"→”Gozaimasu”, which has a similar function with Be-verbs and also ,basically, means "to be or to exist" in a very respected way. But, we never say "Arigatai Gozarimasuru". In some history dramas in the Samurai periods, I hear　by putting the word (koto=thing, siawase/happiness) in between, "Arigataki koto/siawase de/ni Gozarimasuru". It is like hearing phrases from the Shakespearean plays to modern people's ears, I guess... Formal phrases can be transformed in various informal expressions or into dialects. Having said the long trivia, I would not recommend to focus on etymology too much when you are beginning to study Japanese, although it is fun to know stories behind the words and it will make your knowledge beautiful in future.

Hah! Great question. I've known a little Japanese for over 40 years and never really thought hard about the meaning behind the words; I just learned what to say and when. So, I looked it up on the Internet. You can find the answer to your question here: http://en.wiktionary.org/wiki/%E3%81%82%E3%82%8A%E3%81%8C%E3%81%A8%E3%81%86%E3%81%94%E3%81%96%E3%81%84%E3%81%BE%E3%81%99 Basically, "arigato" means "welcome" but not in the sense of "welcome to my house" but rather "your kindness is welcome (or gratefully received)". "gozaimasu" is a formal way of saying "it is". So, if you say "arigato", it is like saying "thanks!" whereas "arigato gozaimasu" is more like saying "I am grateful ( to you)". If you are talking to friends or siblings, you can say "arigato" but if you are talking to a teacher or a boss, you should say "arigato gozaimasu" or even "doumo arigato gozaimasu" which would mean "I am very grateful (to you)".