You get the Cut HM from the captain in the ship departing Vermillion City. He will be in the captain's room after you've gone far enough in the ship and after battling your rival.
In the future next time, if you're stuck on something or need to simply find one item, you can easily google it and find it very easy.