A regular hexaflexagon is a sequence of 3n equilateral triangles on a straight strip of paper folded into a shape of a hexagon. One can perform specific folding/unfolding actions (V-flex, Pinch-flex) on the hexaflexagon, which becomes a flat Rubik\'s cube containing millions of faces. We tackle the problem of regular hexaflexagons of any order. We show that there is a surprising connection between Catalan numbers and the size of triangular regions that make up the hexagon. Based upon this connection, we can provide closed formulas for the number of such triangular regions, to replace previous counting formulas that were algorithmic. We show that for any regular hexaflexagon, constructed from a straight strip of paper, one can always determine the orientation and face up/down properties of any triangle on the strip of paper. Then we explain how one can construct a regular hexaflexagon of any order, based on an "alternating binary tree" model. These results were implemented as a Java applet which we provide online (http://math.georgiasouthern.edu/~bmclean/flex), as a tool for studying regular flexagons of any order.