Domain name labels can technically contain any octet value, but usually they only contain alphanumerics and the hyphen and underscore characters.
This comes from recommendations in section 2.3.1 of RFC 1035:
The labels must follow the rules for
ARPANET host names. They must start
with a letter, end with a letter or
digit, and have as interior characters
only letters, digits, and hyphen.
There are also some restrictions on
the length. Labels must be 63
characters or less.
The underscore character is a more recent addition, typically used in the label portion of SRV records.
You could also permit the "." character if you're going to let users create their own subdomains.
The values that are possible are:
A record - must be a dotted-quad IP address
CNAME record - must be some other legal label
MX record - 16-bit integer priority field, and a legal hostname. NB: some people put in labels which themselves point only to a CNAME record. This is frowned upon.
TXT record - anything you like!
Note that in every case, if you do allow any of the characters not in the normal set they would need to be escaped if they're being stored in a BIND format zone file.