I don't think I've ever noticed M before.
H and S are Hurricane and Tropical Storm.
M must be new this year - I hadn't noticed it before either. From the Forecast Positions legend on the map, it looks like M denotes winds predicted to exceed 110mph at a forecast position. Since 111mph is the lower bound of Category 3 on the Saffir-Simpson Hurricane Scale, my guess is that M stands for "Major Hurricane".
I believe that it is a 'Major Hurricane'. Major hurricanes are defined as being of Category 3 or greater. The wind speeds in the definition of a Category 3 hurricane on this page http://www.nhc.noaa.gov/aboutgloss.shtml matches the wind speed classes in the legend on the map.