Start the scenario by scouting aggressively! Since you don't really have any scouting assets at the start, this needs a bit of explanation.
The fastest way to produce a new scout is for all your villagers to immediately build a Stable and House. It isn't necessary to be that extreme; a Stable and Town Center will do. After that, put all the villagers to work building a castle, while producing one Scout Cavalry and two villagers. Not only is the castle very important for defense, but it also supports a lot of population. When the castle is finished, 5 villagers start processing sheep, and the sixth one starts building a monastery. When the monastery is ready, immediately produce two monks, while the sixth villager starts to build walls. All your food income should be allocated to new villagers until you have at least twenty.
Your regular troops should help with the scouting. Advance them to approximately the edge of what was visible at the start of the scenario. As you do this, you should pick up about 5 sheep. After that, use some of your cavalry to explore territory that seems reasonably safe. It will quickly become clear that the top and right map corners do not contain enemy bases or units, and the cavalry can be used to confirm this. Heavy cavalry should not be used to explore completely unknown territory, because it is too easy for them to run into unhealthy situations, due to their poor sight range, although they might be able to run away afterwards.
Let your first scout complete his run into your base before you give him new orders. He doesn't tell you anything useful, but you don't know that a priori. Send him either right and down, or left and up. Your new scout goes the other way. It doesn't really matter which option you choose, although there may be some minor details that are different. Keep the true scouts oriented towards the enemy positions, because they will see threats before they become dangerous.
Your enemies are already scouting at the start of the scenario. One villager runs right through your position. There is also a cavalry scout wandering around. The main point is that if you dally, you will not get as many sheep as you might, but as long as you act quickly and properly, you will get them all. Either you get them first, or you intercept them afterwards. There are 11 more sheep in the right part of the map, and 10 more in the top part, giving you a total of 26, which means approximately 2210 food. Actually, if you do it right, 5 villagers can reliably get 86 food from a sheep.
Don't run into the main enemy bases at this time. This restriction will allow you to explore about 40% of the map, from approximately the 11 o'clock position to the 5 o'clock position, not including Jerusalem.
Raiding outside Jerusalem
About 5 minutes after the scenario starts, game time, you should have completed the initial scouting phase. All 26 sheep should be in your base. You should have two monks and several new villagers. There is a relic in the right map corner, but leave it there for now, at least until the situation stabilizes. You will have encountered some of Jerusalem's buildings outside their wall, but leave them alone for now. You will have encountered a Hospitaller mining operation outside their base.
You have 10 gold mines in your base area. You will have found 4 more near the Hospitallers, 5 more near Jerusalem, and more. As is normally the case, gold is plentiful in this scenario. Even 10 gold mines will finance all your expenses, unless you send your troops out to commit suicide in large numbers. You have 7 stone mines in your base, and you will have found 7 more near the Templars. This is in addition to your initial stockpile, which is enough for one castle plus your entire main base wall. You may revise your opinion later, but at this time it looks like stone is also plentiful.
Start raiding the Hospitaller mining operation. Be prepared for a serious response. Maintain a presence in that area, because it is their weak point and will be a continual drain on their resources.
About 10 minutes after the scenario starts, your main base wall should be finished. It should consist of four wall sections, separated by three cliff sections. You don't have the map space to build a Wall Maze Complex yet, so a simple continuous wall is necessary. Keep in mind that if your wall is continuous, your enemies know that they must go through it by main force, and they will attack wherever they please. This is fine by you unless they use heavy siege equipment. There is a dirty trick available, which is to have units stand in a gate. Then your enemies are liable to try to walk through that gate. As if, eh, as if!
Send a monk with an escort to pick up the relic now. Send a scout to keep an eye on the stone deposit near the Templars. Blow up the Templar monastery outside their base.
All three of your enemies are scouting your position by now. Serious attacks will be arriving soon. They consist of heavy infantry, spear infantry, archers, heavy cavalry, monks, and all types of siege weapons except heavy artillery. None of this presents a significant threat, as long as you have a second castle in your base, catch most of the siege equipment on the march, and keep your mobile troops away from the enemy mobile troops. Don't build a third castle in your main base, because you shouldn't need it, and it is better to save your stone for other uses. The large stone deposit outside your base will not realistically be available for a long time.
Build up to maximum population. A good roster is 25 villagers, 10 monks, 10 Mamelukes, 5 Light Cavalry, 5 cavalry archers, 8 archers, and 4 each Camels, trebuchets, and Bombard Cannons. When you reach the population limit, you can start converting enemy heavy cavalry. Jerusalem should be up to Cavaliers by then, and they are worth recruiting. In practice, though, any enemy units that get close enough to your monks to be recruitable will immediately be blown away by your automatic defenses.
Harass the Templars and Hospitallers as much as you can. It won't be too long before their new production is only villagers. You still can't approach their Town Centers with your mobile forces yet, however, and it's too dangerous to expose your heavy artillery over there. Nevertheless, it may actually be possible to break them without siege weapons. The AIs love to hunt. They will send their villagers across the entire map to do so. If you camp out near the hunting spots, you can kill an awful lot of enemy villagers cheaply. The AIs will even send their last villager out to hunt, even if it means certain death. If you really want to play dirty, you could drive a deer into a partial enclosure near your fort and watch the carnage.
Eventually, only Jerusalem can maintain a field army. Jerusalem's biggest weakness is that their city doesn't have many gates, and most of them are on the west side of the city. Therefore there will be time periods when you know that there are no enemy mobile troops in the field. This allows you to bombard Jerusalem's static defenses with impunity, if you stay away from their gates. The obvious initial targets are the two Towers near your base. Attacking those Towers will provoke an enormous response, but your trebuchets should be packed up and heading for safety before the responders arrive.
About this time, the Hospitallers and Templars seem to revive. Don't worry about it; just keep grinding away at them.
After defeating the large counter-attack, your next mission is to explore the rest of the map. Going through the Hospitaller camp is unattractive, because they produce lots of Scorpions. The Templars produce lots of heavy cavalry, but no missile troops. The Templar lumberjacks have conveniently opened up a new route into their base by now, and you will take advantage. Send a strike force of one Light Cavalry and 5 Elite Mamelukes into the Templar camp. Fully upgraded, 5 Mamelukes are instant death to a knight, and also to foot knights and villagers. With the speed upgrade, which Teutons don't get, a Mameluke can run circles around a Templar knight, turning around every so often to hurl a lightning bolt. The bottom line is that this force will annihilate the Templars, except for their Town Center and its immediate vicinity. The Templars do have several Towers around their base, but they can be avoided.
After devastating the Templar camp, keep exploring around Jerusalem in a clockwise direction. The next target of opportunity that you will encounter is a Templar-Jerusalem trade route. Just make like any Crusader bandit. Then you encounter and destroy Jerusalem's forestry operation west of the city. Then you complete the circle at the west side of the Hospitaller camp. You find another relic there, all wrapped up and waiting for you. Don't find the Jerusalem castles the hard way!
You do not find any castles outside Jerusalem. However, the Templars and Hospitallers keep producing lots of castle units, so they must have castles inside the city. They could even have significant infrastructure in the city, which means that you will not be able to kill them off completely soon.
About this time, you will have completed all meaningful research. For example, there is no need to research Heavy Camel, as long as you limit yourself to the four starting ones, and you don't need to research any infantry upgrades. This means that you don't need any more resources, so all your villagers can be used in combat roles. You could also disband some of them and produce more troops, but that is hardly necessary.
Crushing the religious orders
The next target needs to be the two Town Centers outside Jerusalem. In principle, this is reasonably safe, because your trebuchets will be invisible to your enemies before they attack, assuming you do things properly, and they blow up a Town Center so quickly that they will be packed up and headed for home before the response arrives. However, the run for home proceeds at a walking pace, so you might lose some trebuchets. Therefore, you should really build a wall compartment near the enemy base first and use that as a jumping-off point for your attack. Deal with the Hospitallers first, because they are rather closer to your base. When this operational phase is completed, you will be able to safely collect the stone outside your main base, which will allow you to build at least two more castles.
Build the wall near the Hospitaller camp, blow away the Town Center, rush some cavalry in, kill all the villagers, raze the Siege Workshop, and retreat. Jerusalem will start to beat on your wall, but you don't care, because that wall is now unimportant.
Dealing with the Templars is a bit trickier. First of all, they have some static defenses, so your trebuchets will need to redeploy several times. In addition, they have a leader unit, the Master of the Templar, who generally patrols their base area. You definitely want to recruit, not kill, him, so you need to lure him over to your monks somehow.
Your enemies are very weak by now, and this time, it's for keeps. Move a large strike force to the ruins of the Hospitaller camp. Then just cruise around the city in a counter-clockwise direction, blowing stuff up as you go. Replace Jerusalem's gates with your own. When you have completed this circuit of the city, you will have destroyed one castle from each of your enemies, lots of other production buildings, some Towers, and lots more troops, and any remaining enemies are now sealed into the city. At some point, they will start to beat on one of your gates, but that is not a serious concern. It isn't necessary to do it exactly like this, but this procedure seems to be the most reasonable one.
You have now explored 96% of the map, everything except the middle of Jerusalem. The final Tower is somewhere in there. The Hospitallers are completely dead now, but you can't completely kill off Jerusalem and the Templars until the very end. You can expect to have to deal with a bunch of monks right before the bitter end, because that's all your enemies can still produce. Basically, all you need to do now is rush a bunch of heavy artillery into the city center and blow up the last Tower. Just don't miss; there is a monastery right beside that Tower!