I have found this :
http://blogs.esri.com/esri/arcgis/2011/11/21/adding-labels-to-arcgis-online-web-maps-part-1/
a small summary :
�?� design labels for your map layers in ArcMap;
�?� convert labels to annotation;
�?� use the Feature Outline Masks tool to create polygon feature geometry from annotation;
then you choose you you want to import the features in your map (services or shapfiles).
With best regards
mh... Have you zipped your shapefile ?
At which step you get the error ? Can you upload your data and then you can't visualize the features ?
Check that you feature class (from annotations) doens't contain more than 1'000 features. If it is so, just divides your feature class (from annotations) in a few shapefiles.