I think it's fair to refer to the other answers for the question, but I would like to add the following:
If you have password rules then also present them on login as well as register.
This way any of the massive number of users who prepend a 1 or a ! to the end of their commonly used simple password will have a useful reminder.
Many users just repeatedly use a common dictionary password. If they've been pushed off this track by complex password rules then they might not remember your site has complex rules in the first place, reminding them will help them to think of what they might have entered, i.e. did they use the complex password they use repeatedly when they need to, or their common password with a special character prefix, etc.
So aside from presenting the password rules on register which is not a commonly used password related page the rules should also be displayed on the login page which will be used much more often.
Something along the lines of 'for security reasons we required you use a password with one special character' near the password field.
This suggestion is based on three pieces of provable evidence ...
- that users choose poor passwords en masse.
- that users re-use the same password for many things
- that users often have poor memories for things like passwords, especially when a long time lapses between usages and with visual memory removed through password obfuscation.
... and then on the deduction that a user who chooses a dictionary password is not suddenly going to choose a random string of 15 keyboard characters just because a special char is required. Therefore there's a good chance you could jog their memory. It would be an interesting test, though I can find no such test online.