The Middle Ages plays somewhat like a reverse capture the flag game but also allows credit for bringing in other players flags to that 3rd location, which you have to fight your way into.
The Domination victory conditions can be ignored, if you persure them with a proper civ, your likely to also trigure a VP victory that way just short of domination even without sending in flags.
As the Turks:
REX out as much as possible in early game, but keeping your empire together. It would be especally helpful if you try to aquire the luxaries SW and S.
In fact much like the standard game.
But as REXing winds down, you also need to start thinking about conquests, so start building your Saphri UU [I forget if you can build them as cheaper units and upgrade, your Saphri are pretty cheap anyway.] And when you have a half dozen or so, start conquering. Initally focusing on luxaries. There's no AI that can stand up to your UU.
Wonders: Doomesday Book is easy to get and will help reduce corruption.
Techs: I considered it "cheating" in my game to try to aquire foreign types [their cheap], so just beeliened into the second era, got the one for Doomesday book, and proceeded to beeline thru the Arab tree, winning shortly after finishing the arab portion not reseaching the final era at all.
As the Abus:
Similar to the Turks only don't pick a fight with Turks.
Jersuleum doesn't produce nearly enough VP to win sitting on your @$$.
It might be possible if you get defeat the Bryanztines with Turkish help to go on and take one or more Christian relics and then transport them back to Jersuelum yourself.
As the Cordvians:
I'm thinking try to conquer Europe. This means beelining to your UU, building some and then annexing Spain. Next is the Franks, followed by Burgundy, and then Germany. It may be wise if you start having to face Knights to stop the war of conquest and settle for returning the relics you captured to Jersuleum.
As the Arabs in Libya:
By far the worst quality land of any Arabs. Start with conquering the Abus to get better land.
As any of the playable Vicking civs:
Techs: Beeline thru Vicking techs
Tactics: Inital goal is to with Berskers land on towns just long enough to steal Christian relics in Northern Europe. Depending upon exactly which civ, there's some fertile territory that might be worthwhile developing to speed along the Vicking Epic which will be handy when the time comes to transport a large stack of units there. (The one in Rome can be taken in route)
As any of the playable Christian techs
You have a distinct disadvantage with units compared to the Vickings and Arabs that doesn't start to get better until you have Knights.
Depending upon your exact civ, you may be able to aquire some of the other relics to bring along with yours either before or in route. Timing is the key.
It's probably easier to take Jersuelum by the sea (and leave the Bryzantine empire alone as a shield) even as the German nation.
But not entirely clear because of timing of Knights vs Galleys.
Probably best to time completion of the Holy Roman Empire to finish the last two Christian techs.
A peaceful player as the Christians might also be able to eliminate the need to capture other relics by both completing the tech tree and building several wonders, but probably still needs to bring a relic in to Jerseulum to win prior to hiting the turn limit.