手土産は何を持って行こうか。って英語でなんて言うの？

この場合は、一緒に行く奥さんと何を持って行こうかと相談しているのだと思うので、
what 「何を」
should we take 「私たちは持って行くべきか」
with us 「自分たちと一緒に」
という具合になります。

今回のケースでは違いますが、例えば、あなた一人で行く場合、両親の家に電話をして「手土産に何を持って行こうか？」ときくなら What should I bring with me? になります。

what 「何を」
should I bring 「私は（あなたの元へ）持って行くべきか」
with me 「私と一緒に」

おっしゃられている内容は以下のようにも表現できると思いました(^_^)
What do you think we should give them?
「私たちは彼らに何をあげるべきだと思いますか？」

この場合、「手土産」の直訳に当たるような言葉（辞書を見ると、calling presentやhospitality giftなど載っていました）は必要ないと思います。

以上です。
少しでも参考になれば幸いです(^_^)

★★大阪カフェレッスン英会話講師KOGACHI