I'm not sure about the situation in Belgium, but kijken can be combined with a direct object in the Netherlands, although it may sound a tad informal to some people. I will stick with (be)kijken, as this transitive verb will make things a bit easier than kijken naar.
All three sentences are possible, but there's a difference in emphasis:
1. We (be)kijken vaak dit programma samen. (Samen is emphasized.)
2. We (be)kijken dit programma vaak samen. (Samen is emphasized.)
3. We (be)kijken vaak samen dit programma. (Any element can be emphasized in this sentence.)
Two other possibilities:
4. Vaak (be)kijken we samen dit programma. (Any element can be emphasized, but more often than not it will be vaak.)
5. Vaak (be)kijken we dit programma samen. (Samen will most likely be emphasized.)
The difference between (1) and (2) is marginal. Vaak can receive secondary stress in sentence (1) more easily, as it is further away from samen, but that's about it.
The main trouble is vaak. Adverbs of frequency can occupy quite a few slots in the average Dutch sentence, but not just any sentence. This is where the headache starts.