Parfum Palace at the end of Route 6. There will be four "mazes" in the backyard (though they're not hard at all). You can find HM01 Cut in the bottom left maze in a yellow pokéball lying on the ground.
Eventually the game will lead you there, so you don't have to go out of your way to find the place or anything.