To "breathe deep" is a common idiom, meaning to fully absorb the atmosphere or flavor of a place/event/situation, as well as just to take a deep breath (for instance to calm yourself). Your example is using it in the sense of absorb and connect with the atmosphere. Collins Cobuild has some examples, e.g.
Stand still, breathe deep and you can hear it in your deep heart's core.
I stand on my balcony and breathe deep.
The first here is about breathing deep in the sense of absorbing and connecting with the place or situation and feeling it in your heart - it's more than just a literal deep breath.
For the English learner, there are three issues with Martin's sentence: punctuation; "breathed" vs "breathing"; and "deep" vs "deeply".
"Breathed" here is a simple past tense; it would be more standard to have "and" than a comma before it ("He looked at the stone figures all around them and breathed deep...") but this is literature so you can punctuate how you choose. Here the use of a comma indicates things happening more closely together or at the same time, while "and" might imply things happening one after another.
One difference between "breathed" and "breathing" is that "breathing" implies continuing action, while "breathed" could refer to taking a single breath; "breathing deep" might imply panting.
As to "deep" vs "deeply", both are valid adverbs. English has many pairs like this where something can be an adverb with or without "ly", e.g. quick/quickly. In the idiom "breathe deep", "deep" is common. In other contexts, "deeply" might be more common, e.g. "I love you deeply." But "breathed deeply" would not be wrong - just longer.
In summary it's a combination of a common idiom meaning "to absorb the atmosphere of a place", with simple past tense for completed action, and a comma for speed.