「ごちそうさまでした」 is a construction of ご (polite prefix) ちそう ("feast/wonderful food") さま (something like "state (of affairs)") and でした, the polite past tense marker. So in a way, it's like you are saying: "It was a wonderful feast"! It can also be shortened to 「ごちそう」, which is more casual in tone.