tl;dr
You should show all valid or all invalid characters before the user starts to type into the field. This should be a hint. Keep it short, easy to understand and straightforward.
Demonstration

download bmml source – Wireframes created with Balsamiq Mockups
In depth explanation
Example placeholders
Use fields with a placeholder that shows a valid example input. Example placeholders indicate the preferred format of the input. This could help for example in a telephone number field.
Message on focus
Display a fixed label or a popup bubble when the user enters the field.
The user will see the hint before he starts to enter the input, so he can think of a different value if the one he wanted to entry is incorrect. This also solves the possible question that a user would ask before giving the input: "what should I write over here? Will my input correct?".
Short and bold character list
Use short form of the valid characters like "a-z" not something like "alphanumerical only".
It's much easier to oversee and understand the accepted characters. You don't have to find out the meaning of the words like: "ok, alphanumerical characters are characters from a to z with numbers". Also clarifies obscurity like: "are uppercase letters allowed?".
I would also recommend @NonNumeric's solution with using bold on the allowed character list. This guides attention to the essence of the popup message.
Feedback on blur
After the user filled the field and the focus is lost, you should validate the field.
- If the input is valid, show a check mark that indicates the valid input.
- If the input is invalid, leave the popup there and make it or the user field (or both) red, so it will indicate that something went wrong.
Thanks to this, if the user missed the guide before typing, he has a feedback after his input. The errors/check marks also simplify the overview of the filled form.
insert-relevant-regex-here
," because then there is no ambiguity about allowed characters, Unicode, allowed lengths, or any weird restrictions that some sites seem to like. Unfortunately, most users do not know regular expressions, so this is unlikely to ever happen.