Learn Icelandic: Við getum ferðast með hverjum sem er.

The preposition með dictates the case here, and when it means 'together with', it requires the dative case. When declining a multi-word pronoun like hver sem er, only the first word changes. The dative form of hver is hverjum, while sem er remains frozen.

Is hverjum strictly masculine here, or does it cover all genders?

It covers everyone. When hver sem er is used to mean 'anyone' in a general sense, it defaults to the masculine form. You use hverjum sem er regardless of the actual genders of the people you might travel with.

If I changed the sentence to past tense ('We could travel...'), would sem er change to sem var?

No, the phrase hver sem er is a fixed idiom. The sem er part stays exactly the same no matter what tense the main verb of the sentence is in.

Why does the verb ferðast end in -st here?

Ferðast (to travel) is a middle voice verb, which is why it has that -st ending. It is in the infinitive form here because it follows the modal verb getum (can). Middle voice verbs keep their -st ending even in the infinitive.