I originally used to double-sided sticky paper to install my travertine tile pieces to the wall, but some have come off and some are loose. We didn't space them at all just did a pyramid type placement, so no grout is involved.
With travertine you should be using thinset to apply it to the wall. You don't really need to grout - I have seen it done either way travertine. If you don't grout then make sure you use a darker grey thinset as it cures into more of a mortar look and also make sure that the thinset isn't squirting up out of your tiles. So there is a little cleanup to do after applying the thinset.