The full phrasing, without leaving out any words, has an infinitive form:
We should go to see a movie.
Leaving out "to" and just using the verb "see" is OK, but it is chopped phrasing. If you want brevity, leave out both "to" and "go":
We should see a movie. We should watch a play. We should eat dinner.
All of these can be filled out, unnecessarily, with "go to do" or "go do" phrasing:
We should go eat dinner. We should go to watch a play.
For something (not) done in the past, you can use the phrase "have gone" and use the full infinitive -- if you are emphasizing the "going" action -- or just use past tense:
We should have gone to see the play. We should have gone to play tennis.
We should have seen the play. We should have played tennis.
The use of "go" in all its forms in these sentences is really unnecessary, but common. It puts an emphasis on (or at least includes) the movement or travel part of the action of the sentence, rather than just the ultimate action -- see, eat, watch, play.