The second sentence is correct:
“He will marry her before he travels to Australia.”
In complex sentences using “before” as subordinating time conjunction, it’s not grammatically correct to render two separate, independent, and nonsimultaneous future actions—one in the main clause and the other in the subordinate clause—both in the future tense. Doing so would make them appear to be simultaneous future actions (contrary to the premise that they are nonsimultaneous), as in the first grammatically flawed sentence you presented above:
“He will marry her before he will travel to Australia.”
When two clauses denoting future actions are linked by the subordinating conjunction “before,” those two actions obviously won’t be simultaneous, so the sentence must make it clear that one of the actions will occur earlier than the other. This sense is conveyed by making the earlier of the two actions take the future tense and the later action, the present tense. This was the case in the first sentence you provided, which is the grammatically correct construction:
“He will marry her before he travels to Australia.”
Conversely, when two clauses denoting future actions are linked by the subordinating conjunction “after,” the later action takes the future tense and the earlier action, the present tense, as in this sentence:
“He will travel to Australia after he marries her.”
These, as I said earlier, are the proper ways of using the tenses in complex sentences involving nonsimultaneous future events.