Enable Birth Island
You normally cannot access this island in the game. Without cheating, the only way to enable Birth Island is to attend a Nintendo event with your Game Boy Advance in hand. There, you can link up your game with the Nintendo event computer to enable Deoxys and Birth Island. However, these events only occur once every few years and there is no guarantee one will ever happen near your home or even in your country. Instead, enter the "Action Replay" cheat code "07CF2578 E43B4EBF" to turn on the island.
Sail to Birth Island
Start by traveling to Vermillion City, the hub which you have visited many times already in your adventures through "Pokemon LeafGreen." Walk to the port and look at the available options. In order to sail to Birth Island, you will need an Aurora Ticket. If you attended a Nintendo event, you can get one of these tickets from a Wonder Gift in any Pokemart. However, it is much easier to simply use the code "641B9F5D 3A0D0482" to put an Aurora Ticket in your inventory. With the ticket in hand, sail to Birth Island.
Solve the Puzzle
You will see a black triangle in the middle of the island. Walk next to the triangle and press "A." The triangle will teleport to another location. Quickly walk toward the triangle and press "A" again. Continue until the triangle turns red. Make sure you do not step on the triangle; if you do so, or if you are too slow, the triangle will reset and you will have to start over. After 11 repetitions, Deoxys will attack.
Capture Deoxys
Fortunately, Deoxys is not a difficult fight. He will be level 30, so make sure your Pokemon are level 30 or more. You will want to use multiple Ultra Balls to capture him. In each game in the series, Deoxys spawns with slightly different statistics. In "LeafGreen," he will have higher HP, Defense and Special Defense than normal, but will have lower than average Speed, Attack and Special Attack. Either way, you should have no trouble capturing him.