PADI Master Diver? Taking some specialties and paying a fee.
NAUI Master Scuba Diver? Taking a whole course which may not be as in-depth as a college for-credit course but which is certainly packed with knowledge compared to others. I don't think, for example, that there's a PADI Physics specialty (that information is reserved for PADI Divemaster), but diving physics is certainly a significant portion of NAUI MSD (physiology is another doozie). Also, my shop won't allow you in the NAUI MSD course until you have at least 50 dives, as you need experience in order to understand and participate in the discussions which made up the most significant portion of the course.
A true master diver? Having all the basic knowledge you'd get from NAUI Master Scuba Diver, PADI Divemaster, or equivalent, plus all the additional knowledge you deem relevant to add to those basics. Additionally, having the in-water skills you'd have wanted your instructors to have (whether they were exemplary displays of such or rather thorough counterexamples). So, basically, having the education, training, and experience to have an innate sense of diving, a comprehensive understanding of the science of diving, and jealousy-inspiring skills proficiency (such as that which is able to make new and old divers alike drool through their regulators and think, "I want to be like that, someday").