Maze moves accumulate from science you produce (but not science you buy), dowries, and from getting the maze bonus when someone else does the maze.
The amount of science it takes to get maze moves is dependent on the amount needed to get the tech, so yes, in the late game it can often seem like it takes forever and a day to get even one new move. Also, the maze minibonus changes depending on civ size.
Maze moves reset if the tech you are in is completed, as well.
You can maximize your moves by co-ordinating to get the minibonus (when someone completes a maze, everyone in the same civ who is in the tech gets the "civ" bonus), and by hoarding science until you get enough moves to complete a maze and get the big bonus.
Also, you can move between uncompleted techs, so if one tech has an easy maze, do the maze, get the bonus and then move to the tech you actually want. Co-ordinate with Science Minister to reduce tech cost - remember that era techs do not reduce in cost, so it is rarely a good idea to have your SM in the era tech.
Culture builds up faster in part, I think because you get those +5s automatically from anyone in your civ doing the puzzle, but you have to be in the same tech to get the maze minibonus.