Your character initially appears in the Lands of Lord British just east of Britain and the The Castle of Lord British. You may want to head to town to buy equipment or food, give Lord British money to gain hit points, and otherwise begin customizing your character. You can Transact with the king, and he will tell you to find the The Tower of Knowledge. You won't be able to complete this quest until you have some means of traveling over water, and it is strictly optional.
At this point you're free to explore the continent. All locations in the Lands of Lord British are accessible on foot, with the exception of the two landmarks and the dungeon in the middle of the inner sea (Mondains Gate to Hell). All eight towns are basically identical, though there are two different lists of goods in the weapon shops depending on which you enter. You can only buy a Raft or Frigate in a town next to water. The nearest complementary weapon shop to Britain is in Paws to the northeast.
Your main goal is to complete the quest given to you by the king in the The Castle of the Lost King. The castle is northwest of Paws, on the north shore of the continent's inner sea. The king asks you to kill a Gelatinous cube, a dangerous monster that can be found on Dungeon Levels 3–4 of any dungeon. You may have to upgrade your hit points and gear (and possibly your stats) before you're tough enough to take on this challenge, but once you're ready, you can head to any dungeon in the land. You can either explore the dungeon to find your way down, or make use of the Ladder Down and Ladder Up spells to quickly reach the appropriate floor. If you plan to explore, make sure to bring several Rope & Spikes to help you avoid pit traps. Once you have defeated a Gelatinous cube, return to the The Castle of the Lost King. The king will give you the Red Gem and tell you that you will need all four Gems to power the Time Machine. If you've heard enough hints at local taverns, you know you will need the Time Machine to defeat Mondain, so it's time to find the other kings with Gems.
Those other kings are found on other continents, so you will need some means of traveling over water to reach them. Purchase a Raft, Frigate, or Air Car (which becomes available at level 4) in a coastal town to begin your journey. Now is a good time to find the The Tower of Knowledge and start increasing your stats via landmarks. With that done, your required time in the Lands of Lord British is over.