How to address drywall damage and wet grout from my Travertine tiled shower?
Without knowing how sever the water damage is inside the walls there is no way of telling exactly what will be required.

If, as it appears,  the whole tile job was  improperly installed on   drywall, ( Sheetrock ) not a proper waterproof substrate, then there could be significant mold, mildew ( as evidenced in the second photo ) and wood rot.  This would require completely gutting it and starting over.

You could spend many hours removing a re-grouting but that does not address the root of the problem. Water saturated drywall can not be left to "dry out" and mold inside the wall NEEDS to be removed. 

If it has been happening for years than wood rot could be an issue. Any rotten wood will need to be accessed to see if it needs be replaced as well.  

You could cut out the rotten drywall next to the tile and see if you can get some visuals from inside the wall,  A endoscope type camera may help, ( there are cheap-ish ones available for your phone. ) You will only be able to see inside that one stud cavity but it will give some more clues and allow air in the space. 

Porous tile and grout will let water through so it is imperative that the substrate behind it is water proof.  

The bottom line is there needs to be more exploratory assessment before a compressive plan can be formulated.