OK, you do need ArcGIS for Desktop 10.1 or greater. You can't publish from earlier versions. MSD files are not supported for upload. In 10.1, you can publish directly, and the service definition file (.SD) is created and uploaded, and a service gets created from it.
Without 10.1, you can zip up the contents of a shapefile (all shapefile files, e.g., .shp, .prj, etc in the zip), upload that directly from ArcGIS.com and publish a service from it. Once you have a service, you can add it to a web map.