As you were told in Britanny, ask Sir Sean of the Lycaeum about Stonegate, and he'll tell you how to get there, but he'll also emphasize that you need a item to cross mountains.
Strange and exotic items can be found in Buccaneer's Den. Talk first to Lord Dalgrin, who will direct you to the easy-going Tierra. Be kind to her, and she'll tell you that Bidney used to climb mountains. But the drunk pirate doesn't have his tool anymore: he gave it to Lord Michael of Empath Abbey. Therefore, you should just go to the Castle of Love and ask him of the grapple, and he'll give it to you.
Now that you have the grapple, you can reach Bordermarch and talk to Sir Simon, who will tell you about the powers of the Crown and the location of the Sceptre, that is Stonegate.
Also, you need more items before going to Stonegate. Go to Britain and talk to the cook Justin: he'll start the trail about glassware. Talk to Eb in the same tavern, then to Malik of Moonglow, and finally to Sven in Buccaneer's Den, and you'll have all the informations to get the Glass Swords. Explore the mountains with gems to find the exact location; when you get there, search the land, get one sword, equip it to one of your party members, then repeat: this way you'll be able to have one glass sword per party member plus one; unequip them and save them for a fight against the Shadowlords.
If you go to Stonegate now, the Shadowlords are not the only obstacle to retrieve the Sceptre of Lord British: the keep is filled with bottomless pit traps, and you should fly over them. Go to Serpent's Hold and talk to Monsieur Loubet: he will tell you a bout a magic carpet he gave to Bandaii of Paws. This mage, in turn, does not own the carpet anymore, but he will tell you whom he gave the carpet if you can find proof of the existence of a talking horse. Continue to North Britanny and talk to Kurt the stableboy: he'll just tell you the favourite horses of his friend, Treanna. She's a girl working in the stables of Castle Britannia, and if you guess her favourite horses, she'll tell you about Smith the talking horse. With this information you can go back to Bandaii ad learn that the magic carpet is in the private chambers of Lord British atop Castle Britannia. To get in there, you should first avoid Stillwelt the guard, who actually goes to sleep at night, then use either a "magic unlock" spell or a skull key to open the door.
Now you are fully equipped to face the dangers in Stonegate and retrieve Lord British Sceptre. The keep is inhabited by the three Shadowlords, who can get invisible and are only vulnerable to glass swords. The Sceptre is in the central room, surrounded by deadly pit traps.
Note: if the Avatar enters conflict with a Shadowlord while in possession of the sceptre, the Shadowlord will steal the sceptre and return it to Stonegate. The player will have to retrieve the sceptre once again.