"What gift should we get her?"
送 is usually used with gifts rather than 给. Also be careful with the difference between 他 and 她. Here they specify "her", so it should be 她。
I would say that you would rather use 送 instead of 给 to emhasize the act of giving it for free as a gift, 给 simply means to give. Though your sentence is not incorrect.
Hello, is 我们要给她送什么礼物 correct ? It's refused.