In order to establish a mark of a particular order, you have to design the survey so that it meets all the Class and Order requirements (listed in the standards) AND meet the error requirements, which vary depending on the method used (differential or GPS/Trigonometric). The actual position/elevation measurement is fairly trivial, the requirements are designed such that if you meet them, you should meet the closure requirements. Australia has a very well-developed set of national surveying standards, due in part to its history, and land registration system.
Surveyors use existing control points to establish the position/elevation of the new control point. For vertical control, depending on the Class/Order requirements, survey or geodetic-grade GPS or more rarely, differential leveling is used.
High-accuracy GPS surveys involve collections on multiple known points and the new unknown point simultaneously, and the data is then post-processed together to remove systematic error from things like atmospheric effects.
With leveling, you measure the difference in heights between your known points and the unknown point, Level runs start and end on known points, so the error can be quantified very accurately if good techniques are used. This is very labor intensive and requires lots of time and trained personnel, especially if the new point is very far from the known control points.
Generally, the further away the known control points are from new mark, the more work is required for good accuracy, but it is still possible. Systems like OPUS can generate very good results with fairly long baselines and longer collection times.
As for how you can be sure a mark is "right", all (good) survey measurements include a method of quantifying the error and uncertainty. So a mark is considered "right" if its error and uncertainty fall within the accepted standards.