You walk up to a cuttable tree (they're small and fragile-looking), click the A button, and click YES, when the choice box pops up.
You stand in front in a tree and press "a" and it says this is an odd tree want to cut it down so press "a" again and you will cut it down. In a battle just press "a".
First teach the Hm to a pokemon that knows it, then stand near a tree, and press A, it will ask if you want to cut it. just say yes, and the pokemon will cut it down for you.
My answer is the same as all those before me. However, I jsut want to add that in Gen 1, you actually had to select Cut from the Pokemon Menu Screen.
