The Hedge Maze is located in The Naughty Sorceress' Tower. Frank will guide you through the maze. Following his advice gets you topiary nugglets. Ignoring him gets you through quicker, but puts you up against more challenges.
The Tower was revamped in 2015. For the old version of the maze see The Hedge Maze/Old.