You can move it into another geodatabase and ArcGIS should also copy the associated domains with it. Like you discovered, Shapefiles do not support field domains; it needs to be in a geodatabase (File or Personal). And, as Leo D. mentioned, a feature class can only exist in a geodatabase.
If you need to deliver the data to someone in a format other than a geodatabase, you have two obvious options: