He put on a disguise and fast-talked his way into the building, which he had already known his way around
I asked Christopher for some clarification about this at NYCC, and he told me that Murtagh just put on a disguise and talked his way in
How did Murtagh get into Gil'ead's prison? In the self-published [edition], you see a couple scenes of him kind of planning, but we're never told what his actual plan was and how he got in.
He basically just put on a disguise and fast-talked his way into the building. And he knows the building because he's been there as Murtagh, not disguised. So that was really it. He basically just BS'd his way in.
October 2023 Interview
This fits with the hints that are provided in the original self-published edition of Eragon and also the new Murtagh book.
The original 2002 self published edition included several scenes from Murtagh's point of view while Eragon was captured. However, these scenes mostly focus on Murtagh's interactions with Saphira and his preparations for the journey that would come after successfully escaping. While the scenes do lead the reader to anticipate that Murtagh will be attempting a rescue operation, they don't actually reveal what the specifics of his plans were. The closest that they come is that they show Murtagh following the soldiers into the city and hiding in the gutter studying the fortress for weaknesses.
The scenes were cut from the book at the suggestion of Christopher's editor when the book was traditionally published in 2003, because they lessen the surprise to the reader, and also to keep the viewpoint consistent throughout the book. (This was the only place where a different POV was used.)
The passages were later also included as bonus back matter in the 2018 Barnes & Nobles Exclusive Collector's Edition. (Which is alas also now out-of-print, but still easier to get hold of than the self-published edition.)
As best as I can tell these are the most relevant parts:
[Murtagh] hurried after the soldiers.
He caught up with them halfway through Gil’ead and tried to stay out of sight as he trailed them. Whenever someone passed him, he lowered his head to hide his face. He shadowed the soldiers to the center of Gil’ead, where they vanished inside the gated maw of the grim fortress.
Murtagh prowled around the stronghold, examining it for weaknesses. All the doorways were large, well lit, and secured by the watchful eyes of two or more guards. None of the barred windows were large enough for a man to fit through; archers patrolled a rampart on the roof. Murtagh lay in a gutter where he could watch the building. There was nothing to do now except wait. He was unsure of how to free Eragon, but he would think of something. He always did.
Murtagh lifted himself out of the gutter and brushed off his clothes. He had watched the fortress all day, slowly composing a plan. It would be difficult to get inside, but not impossible.
He ate quickly, then explained his plan to Saphira. He finished by saying, “For this to work, I need your help. It’s risky for both of us, but it’s the only way to free him.”
Eragon (self-published Edition) - Chapter 41 - "A Shaded Elf"
[Murtagh] checked his weapons one last time, offered a prayer for luck to whatever gods might be listening, then put on the scruffy cap he had bought. “Are you ready?” he asked Saphira. “You understand everything you have to do?”
She raked the ground savagely with her claws and nodded determinedly.
“Very well,” said Murtagh. He rubbed dirt onto his hands, face, and under his chin. “One last warning: above all, don’t let anything happen to you. Eragon would never forgive me.” Saphira pulled back her lip in a low laugh and stretched her wings toward the sky. “And keep your wings down! An archer would have to be blind not to hit them.”
Murtagh held up his hands as she growled impatiently. “Okay, I’m going. Let’s just hope this works.” He tucked his sword and bow under the tattered cloak wrapped over his clothes, and hobbled toward Gil’ead.
Eragon (self-published Edition) - Chapter 42 - "Du Súndavar Freohr"
In Murtagh, there are a few callbacks to this event, but again, very little is said about the how.
And the time before that had been little better: an ambush and then him having to sneak into the fortress to rescue Eragon from the clutches of the Shade Durza.
Murtagh - Part One, Chapter V - "Dragonflight"
Squatting, Murtagh dug a handful of moist dirt out from under the grass and rubbed it into his hands and onto his face. He hated the feel of the grime, but it would help age him and make him look more like a commoner.
He had a sudden, intense sense of familiarity, as if he’d already lived this moment. In a way he had, he supposed. Before entering Gil’ead to help rescue Eragon, he’d done exactly the same.
Murtagh - Part Two, Chapter IV - "Fish Tales"