I'd just like to expand on a couple of points in lvd's excellent answer.
You might get by with just using a jumper wire to short the reset pin to ground for a brief moment after you've powered up the CPU. It's worked for me, but if you're having problems it's best to build a proper reset circuit.
Many CPUs have a minimum length for the reset pulse. If your reset switch isn't debounced, it might generate a perfectly fine result pulse but then bounce on release, leaving you with a too-short pulse (and possibly a confused CPU) after that.
A 555, of which you clearly already have at least one, works well to generate a pulse of a specific length; just wire it up as a one-shot. Gates with Schmitt-trigger inputs, such as a 74LS14, are also great for generating pulses and debouncing switches, and you can use an spares as regular gates (for address decoding or whatever) as well.
Some examples of the above circuits, and a good introduction to reset circuits, are given in the Reset Circuits section of Wilson Mines Co. 6502 Primer. I strongly encourage you to read through the relevant pages in that primer as you build sections of a computer, such as the clock, reset circuits, address decoding, etc. etc. It will give you a general understanding of the problems and solutions in each area and also give a lot of specific advice on how to avoid pitfalls.
Regarding the decoupling capacitor, 0.1 μF is a typical value; just drop one lead of the cap into the the breadboard column for the Vcc pin and the other into the breadboard column for the ground pin of that chip. (This goes right over the top of the chip for the Z80.) If the two pins are too far apart, and you don't want to take the time to extend the cap with a wire, even just using an adjacent ground rail will still help enormously.
You should do this for all your chips, not just the CPU.
If you have an oscilloscope, run your system with a 1 MHz clock and, with and without the decoupling capacitor, have a look at the waveforms of your clock input and an output such as A0. Freqently you will get a pretty dramatic demonstration of what a decoupling capacitor does for you.