first off, DON"T catch Deoxys your first time around! KO it, challenge the Elite 4 again and then you can fight it again. Use this in order to get the nature you want for it, rather than using the Master Ball and just being stuck with whatever random nature you get.
2) get/catch/breed a bunch of Ralts with the Synchronize Ability. Put them at the head of your party when you are going to fight the legendary you want. It doesn't matter if they're not levelled up and get KOed, their purpose is that whatever nature they have is the nature the legendary you are going to fight will have 50% of the time. This applies to all legendaries you can fight in game with the exception of the first time you encounter a Lati@s during story mode, THAT Lati has a 100% chance of having the nature of your lead Synchronize pokemon.
3) Every legendary pokemon has a guaranteed 3 perfect stats. Save as close to the actual encounter as possible (so if it is standing on the map screen, save right in front of them, for example) put the Synchronize Pokemon at the head of your party, save, then start the battle. Catch the pokemon, run it's stats through an online IV calculator (like at Serebii) to see what stats it has that are perfect (or take it to the battle resort to get the IV checker to tell you) and when you get the stats and nature you want, then continue on. If you don't, simply soft reset and try again.
4) the best Capture pokemon I have seen is Gallade. It takes little breeding, but make sure it has Hypnosis, Skill Swap (VERY handy when trying to find hidden ability pokemon in hordes) False Swipe and Shadow Sneak (for ghost types since they are imune to False Swipe) There are other capture pokemon, however, Gallade can mega evolve in ORAS which is VERY handy when trying to capture legendaries.
5) be patient. Some get caught immediately, others can be very frustrating. Just stock up on Pokeballs and settle in.
That's all the advice I can think of.