From the main gate, just follow the path forward until you get to the wall. There is a lever there to call the elevator platform if it is up, and buttons to operate it. Once up on the higher level, there is pretty much only one way to go, which will lead you to a couple merchants, and a group of people standing around in front of the ministry. Talking to the commander there will give you access to the teleporter shrine, which will let you get into the ministry (or go anywhere else there is a teleporter shrine).
Crabbie is at the start of the fjords (by the entrance from Broken Valley) if you have yet to send a zeppelin to pick him up (talk to Page) or on the ramp up to the zeppelin on the top of the harbour building if you have.
Jedediah is in Dragon Cliff Castle, wandering around at the back, near the entrance to Orobas' Lair.
