No they do not have to store the password in cleartext, they can just analyze it at any time you enter it for compliance.
Some rare cases, the password is analyzed at creation and information about it is stored in cleartext, this would look like contains: x amount letters, numbers, no special characters, ect ect.