Consider gifting them a new set of luggage, a travel pillow, or an experience for their honeymoon, like a couples' massage or a romantic dinner.