A maze is basically a puzzle for your players to solve. So consider the possible ways to solve the puzzle, and build from there. (And remember that while you don't want the puzzle to be too easy, you also don't want it to be too difficult - frustration is a terrible thing in a game!)
So, consider the obvious routes through the maze: what happens if the PCs just follow the leftmost wall? What happens if they use chalk to mark their paths, or lay out string behind them? What happens if one PC has a really good sense of direction? (At least one of these should probably be answered with "they get out, but it is a somehow suboptimal route"; and at least one probably wants to be opposed somehow, because someone moves the chalk markers, or whatever.)
Then consider ways they can short-circuit the maze. Maybe the maze has statues of a man dotted throughout that gradually get older the closer you get to the exit. Or maybe there are signs from some previous adventurer who came through the maze. Or whatever.
And next, and perhaps crucially, you need to come up with some stuff to break up the tedium in the maze. As a rule of thumb, for every fifteen minutes of real-world time spent navigating the maze, something should happen - maybe the minotaur catches up with them and has to be dealt with, or the maze reconfigures itself, or they learn someone has been moving their chalk marks, or... (Perhaps the best "somethings" to have happen are things that force the PCs to abandon their meticulous search - the minotaur is too powerful to fight, so they have to run, or their treasure gets stolen by goblins who have to be chased down, or a slide trap moves them to another part of the maze, or... Otherwise, they're likely to just methodically plod through, leading to a really easy but also really dull time.)
Finally, be sure to have an "escape clause" - as soon as it stops being fun, be sure to say "after X hours of searching, you finally come to the exit. At which point..."