From the Outer Wall bonfire, head into Eleum Loyce and turn left at the intersection just beyond the mangled doors. Follow the path and enter the mist to fight Aava, the King's Pet.
As with every other Dark Souls 2 DLC, there are two NPC summon signs on your path to the boss. The first, Masterless Glencour, is about halfway between the bonfire and the mangled doors. The second, Steelheart Ellie, is just before the stairs leading to the mist and the boss fight.
Our favorite strategy is based on melee weapons because of Aava's high resistance to spells. In short, it relies on staying behind her whenever possible and rolling through her attacks.
Her slashes are powerful and have the potential to kill you in one swipe. She's most vulnerable when you're behind her. Lock on, learn when she's going to swipe at you, and time your rolls to move through her deadliest attacks. Her Dark projectile attack is fairly easy to avoid, and if you see her tense up, get some distance between you and her because she's going to blast you away otherwise.
The video here shows the fight using the two NPCs, who are useful for distracting her. When you defeat here, you'll earn the Soul of Aava, the King's Pet.
Head to the opposite end of the area where you fought her, walk through the door and, ignoring the door that won't open in the structure, up the staircase. Open the large doors to the Grand Cathedral and light the Grand Cathedral bonfire.