PROTIP: Carry a cartridge from a razor or break the head off of a disposable. Use it to shave off any seams that may be present on the tube adjacent to the puncture. Eliminates the ridge that may interfere with patch adhesion and simply makes the patch easier to apply.

Rema patches are the best out there, or at least I have yet to see anything that works as well or as reliably. Any patch system that you use with vulcanizing fluid will tend to work better than one that supplies rubber cement instead, and those with rubber cement will work better than any glueless patch out there (the Weldtite ones not withstanding, necessarily, as I haven't tried them).

I apologize if I missed this already being mentioned in this thread, but when you apply the patch, DO NOT remove the thin plastic the patch is stuck to. If you do it before you apply the patch, you'll likely dirty the surface that is supposed to bond to the tube. If you do it after you apply the patch and before it is FULLY bonded, you'll weaken the bond and the patch will be a lot more likely to fail. What I do is just leave it on until the next time that tube comes out of a tire to be patched again. At that point it's usually about ready to fall off on its own anyway.

Be generous with the vulcanizing fluid or rubber cement and cover an area bigger than the patch. Once it has dried enough (give it a couple minutes, test the very edge where the patch won't be with a fingertip - it should be only a little tacky to the touch). Place the center of the patch over the puncture, put it between your thumb and a finger and, using your other hand for extra strength, press them together HARD. Repeat the process until the whole patch is on there well. Wait as long as you can before you inflate the tube again. Even ten minutes can make a difference.

I carry one tube, and when I get a flat I patch the tube on the spot, but throw my spare in and let the new patch sit for a while. This gives me a 3-tube system, each tube with multiple patches at this point. One in the bag, two on the bike.

Outside of ****ty glueless patches I had to use in a pinch, I have not had a single patch fail in the last two years, and that accounts for 30+ patches total, on my bike and on friends' who I have patched tubes for.