1 Amp FETS
Try IRF7201 or 7101 and Zetex ZVN4306A, both available from Digi-Key.  I've had
good luck with both, driven direct from PIC I/O.  I can't suggest complements,
though.  I have only used the N-channel ones.

Exploding 2N7000
The 2N7000 is probably too small.  Your immediate problem wasn't too little
current capacity, though, but too little power handling capability.  It exploded
because it did not have enough gate voltage (relative to source).  I assume it
saw 4.8V-3V where the bottom one saw 4.8V.  With less gate voltage than required
for minimum on resistance (equivalent to saturation of a bipolar), it is a
resistor and heats up according to I*I*R.  This is the advantage of a
complementary drive circuit.

Two NiCds are only going to give you 2.4 V nominal, and less in practice.  It
will be real hard to make this work.  NiCds have flatter discharge, though.
This means less loss of terminal voltage toward end of discharge cycle.  You
should be thinking about what happens to the battery voltage as the batteries
run down.  By the way, this would all be much easier with 4 NiCd or 3 alkaline
cells.

Motor snubbers:
Try 4.7 to 10 ohm in series with .1uF.  Keep leads short or it won't do any
good.  Use stacked film cap or monolithic ceramic.

200mV on the power supply is not too bad but 500 or 700 (between rails) is
marginal.  The type of capacitor you use on the output of the step-up is
important.  It should have low ESR or low inductance.  Also, paralleling smaller
value capacitors is better than one large one.  You may just need fatter and/or
shorter power conductors.

Motor runs with FET gate open.
Unlike bipolar transistors which (more or less) operate from a current into the
base and therefore will (more or less) turn off when unconnected, FETs are
controlled by the voltage on the gate.  The gate is like a capacitor.  What you
saw is that, once you charge up the capacitor, it stays charged (and therefore
turned on) until the charge can leak away.  When you first hooked up the FETs,
they had a residual charge on the gate, mayeb just from being handled.